Graph Algorithms: Representations, Traversals, Shortest Paths, and Spanning Trees

A graph $G = (V, E)$ consists of a set of vertices (nodes) $V$ and edges $E$ connecting pairs of vertices. Graph algorithms form the backbone of network routing protocols (OSPF, BGP), dependency resolution engines, social network mapping, and recommendation systems.

⚡ Quick Dive

Graph Algorithm Complexity Matrix

📖 Extended Guide

1. Graph Representations

Graph:
(0) ─── [1] ─── (1)
 │       │
[4]     [2]
 │       │
(3) ─── [3] ─── (2)

1. Adjacency Matrix (Dense Graphs: E ≈ V²):
   Space: O(V²) | Edge Lookup: O(1)
       0  1  2  3
   0 [ 0, 1, 0, 4 ]
   1 [ 1, 0, 2, 0 ]
   2 [ 0, 2, 0, 3 ]
   3 [ 4, 0, 3, 0 ]

2. Adjacency List (Sparse Graphs: E ≪ V² - Standard Choice):
   Space: O(V + E) | Edge Lookup: O(degree(u))
   0: -> (1, wt:1) -> (3, wt:4)
   1: -> (0, wt:1) -> (2, wt:2)
   2: -> (1, wt:2) -> (3, wt:3)
   3: -> (0, wt:4) -> (2, wt:3)

2. Traversals: BFS vs. DFS

Breadth-First Search (BFS)

• Traverses layer by layer using a Queue.
• Guarantees the shortest path on unweighted graphs.

Depth-First Search (DFS)

• Explores as deep as possible along each branch before backtracking using a Stack (or recursion).
• Ideal for topological sorting, strongly connected components (Kosaraju / Tarjan), and cycle detection.

// Cycle detection in Directed Graph using 3-color DFS
const (
	White = 0 // Unvisited
	Gray  = 1 // Currently visiting (in recursion stack)
	Black = 2 // Fully visited
)

func hasCycle(u int, adj [][]int, colors []int) bool {
	colors[u] = Gray
	for _, v := range adj[u] {
		if colors[v] == Gray {
			return true // Back-edge detected (Cycle)
		}
		if colors[v] == White && hasCycle(v, adj, colors) {
			return true
		}
	}
	colors[u] = Black
	return false
}

3. Topological Sorting (Kahn's Algorithm)

Topological ordering arranges vertices in a Directed Acyclic Graph (DAG) linearly such that for every directed edge $u \to v$, vertex $u$ comes before $v$.

func TopologicalSort(numNodes int, adj [][]int) ([]int, bool) {
	inDegree := make([]int, numNodes)
	for u := 0; u < numNodes; u++ {
		for _, v := range adj[u] {
			inDegree[v]++
		}
	}

	queue := []int{}
	for i := 0; i < numNodes; i++ {
		if inDegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	order := []int{}
	for len(queue) > 0 {
		curr := queue[0]
		queue = queue[1:]
		order = append(order, curr)

		for _, neighbor := range adj[curr] {
			inDegree[neighbor]--
			if inDegree[neighbor] == 0 {
				queue = append(queue, neighbor)
			}
		}
	}

	// If order contains all nodes, a valid topological sort exists; else graph has a cycle
	return order, len(order) == numNodes
}

4. Single-Source Shortest Path: Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a starting vertex to all other vertices in a weighted graph with non-negative edge weights using a greedy min-priority queue:

package main

import (
	"container/heap"
	"fmt"
	"math"
)

type Edge struct {
	to, weight int
}

type Item struct {
	node, dist int
}

type PriorityQueue []Item
func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any)        { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}

func Dijkstra(numNodes, start int, adj [][]Edge) []int {
	dist := make([]int, numNodes)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[start] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{node: start, dist: 0})

	for pq.Len() > 0 {
		curr := heap.Pop(pq).(Item)
		u := curr.node
		d := curr.dist

		if d > dist[u] {
			continue // Outdated entry
		}

		for _, edge := range adj[u] {
			if dist[u]+edge.weight < dist[edge.to] {
				dist[edge.to] = dist[u] + edge.weight
				heap.Push(pq, Item{node: edge.to, dist: dist[edge.to]})
			}
		}
	}

	return dist
}

func main() {
	n := 4
	adj := make([][]Edge, n)
	adj[0] = []Edge{{1, 4}, {2, 1}}
	adj[2] = []Edge{{1, 2}, {3, 5}}
	adj[1] = []Edge{{3, 1}}

	dist := Dijkstra(n, 0, adj)
	for i, d := range dist {
		fmt.Printf("Shortest distance from 0 to %d: %d\n", i, d)
	}
}

5. Minimum Spanning Trees: Kruskal's vs. Prim's

A Minimum Spanning Tree (MST) connects all vertices in an undirected weighted graph with minimum total edge weight and zero cycles ($V-1$ edges).

• Kruskal's Algorithm: Sorts all edges globally by weight and uses a Disjoint Set Union (DSU / Union-Find) data structure to greedily add edges that don't create cycles ($O(E \log E)$).
• Prim's Algorithm: Grows a connected tree outward from a starting node using a priority queue ($O((V+E) \log V)$). Preferred for dense graphs ($E \approx V^2$).