Complete Guide to Graph Algorithms in Go
Introduction Graphs are fundamental data structures that model relationships between entities. This comprehensive guide covers all major graph algorithms in Go, providing both standard library approaches (where applicable) and from-scratch implementations with detailed explanations. What You’ll Learn: Graph representation techniques Traversal algorithms (BFS, DFS) Shortest path algorithms (Dijkstra’s, Bellman-Ford, Floyd-Warshall) Minimum spanning tree algorithms (Kruskal’s, Prim’s) Topological sorting Advanced graph algorithms Time and space complexity analysis Real-world applications Graph Representation Adjacency List package main import "fmt" // Graph represents a graph using adjacency list type Graph struct { vertices int edges map[int][]int directed bool } // NewGraph creates a new graph func NewGraph(vertices int, directed bool) *Graph { return &Graph{ vertices: vertices, edges: make(map[int][]int), directed: directed, } } // AddEdge adds an edge to the graph func (g *Graph) AddEdge(from, to int) { g.edges[from] = append(g.edges[from], to) if !g.directed { g.edges[to] = append(g.edges[to], from) } } // GetNeighbors returns neighbors of a vertex func (g *Graph) GetNeighbors(vertex int) []int { return g.edges[vertex] } Weighted Graph // Edge represents a weighted edge type Edge struct { From int To int Weight int } // WeightedGraph represents a weighted graph type WeightedGraph struct { vertices int edges map[int][]Edge directed bool } // NewWeightedGraph creates a new weighted graph func NewWeightedGraph(vertices int, directed bool) *WeightedGraph { return &WeightedGraph{ vertices: vertices, edges: make(map[int][]Edge), directed: directed, } } // AddEdge adds a weighted edge func (wg *WeightedGraph) AddEdge(from, to, weight int) { wg.edges[from] = append(wg.edges[from], Edge{From: from, To: to, Weight: weight}) if !wg.directed { wg.edges[to] = append(wg.edges[to], Edge{From: to, To: from, Weight: weight}) } } // GetEdges returns all edges from a vertex func (wg *WeightedGraph) GetEdges(vertex int) []Edge { return wg.edges[vertex] } Breadth-First Search (BFS) Implementation package main import ( "container/list" "fmt" ) // BFS performs breadth-first search starting from a given vertex func (g *Graph) BFS(start int) []int { visited := make(map[int]bool) result := []int{} queue := list.New() // Start with the initial vertex queue.PushBack(start) visited[start] = true for queue.Len() > 0 { // Dequeue element := queue.Front() vertex := element.Value.(int) queue.Remove(element) result = append(result, vertex) // Visit all neighbors for _, neighbor := range g.GetNeighbors(vertex) { if !visited[neighbor] { visited[neighbor] = true queue.PushBack(neighbor) } } } return result } // BFSPath finds shortest path between two vertices (unweighted) func (g *Graph) BFSPath(start, end int) []int { if start == end { return []int{start} } visited := make(map[int]bool) parent := make(map[int]int) queue := list.New() queue.PushBack(start) visited[start] = true parent[start] = -1 found := false for queue.Len() > 0 && !found { element := queue.Front() vertex := element.Value.(int) queue.Remove(element) for _, neighbor := range g.GetNeighbors(vertex) { if !visited[neighbor] { visited[neighbor] = true parent[neighbor] = vertex queue.PushBack(neighbor) if neighbor == end { found = true break } } } } if !found { return nil } // Reconstruct path path := []int{} current := end for current != -1 { path = append([]int{current}, path...) current = parent[current] } return path } // BFSLevels returns vertices grouped by their distance from start func (g *Graph) BFSLevels(start int) map[int][]int { visited := make(map[int]bool) levels := make(map[int][]int) queue := list.New() queue.PushBack(start) visited[start] = true currentLevel := 0 levels[currentLevel] = []int{start} for queue.Len() > 0 { levelSize := queue.Len() currentLevel++ for i := 0; i < levelSize; i++ { element := queue.Front() vertex := element.Value.(int) queue.Remove(element) for _, neighbor := range g.GetNeighbors(vertex) { if !visited[neighbor] { visited[neighbor] = true queue.PushBack(neighbor) levels[currentLevel] = append(levels[currentLevel], neighbor) } } } } return levels } Complexity Analysis Time Complexity: O(V + E) where V is vertices and E is edges Space Complexity: O(V) for the queue and visited set Practical Uses Social Networks: Finding friends within N degrees Web Crawling: Discovering web pages level by level Network Broadcasting: Packet routing in networks GPS Navigation: Finding shortest path in unweighted maps Peer-to-Peer Networks: Finding nearby nodes Example Usage func main() { g := NewGraph(6, false) g.AddEdge(0, 1) g.AddEdge(0, 2) g.AddEdge(1, 3) g.AddEdge(2, 3) g.AddEdge(3, 4) g.AddEdge(4, 5) fmt.Println("BFS Traversal:", g.BFS(0)) // Output: [0 1 2 3 4 5] path := g.BFSPath(0, 5) fmt.Println("Shortest path from 0 to 5:", path) // Output: [0 1 3 4 5] or [0 2 3 4 5] levels := g.BFSLevels(0) for level, vertices := range levels { fmt.Printf("Level %d: %v\n", level, vertices) } } Depth-First Search (DFS) Implementation package main import "fmt" // DFS performs depth-first search starting from a given vertex func (g *Graph) DFS(start int) []int { visited := make(map[int]bool) result := []int{} g.dfsRecursive(start, visited, &result) return result } // dfsRecursive is a helper function for recursive DFS func (g *Graph) dfsRecursive(vertex int, visited map[int]bool, result *[]int) { visited[vertex] = true *result = append(*result, vertex) for _, neighbor := range g.GetNeighbors(vertex) { if !visited[neighbor] { g.dfsRecursive(neighbor, visited, result) } } } // DFSIterative performs iterative DFS using a stack func (g *Graph) DFSIterative(start int) []int { visited := make(map[int]bool) result := []int{} stack := []int{start} for len(stack) > 0 { // Pop from stack vertex := stack[len(stack)-1] stack = stack[:len(stack)-1] if !visited[vertex] { visited[vertex] = true result = append(result, vertex) // Push neighbors onto stack (in reverse order for consistent ordering) neighbors := g.GetNeighbors(vertex) for i := len(neighbors) - 1; i >= 0; i-- { if !visited[neighbors[i]] { stack = append(stack, neighbors[i]) } } } } return result } // HasCycle detects if the graph has a cycle (for undirected graphs) func (g *Graph) HasCycle() bool { visited := make(map[int]bool) for vertex := 0; vertex < g.vertices; vertex++ { if !visited[vertex] { if g.hasCycleDFS(vertex, -1, visited) { return true } } } return false } // hasCycleDFS is a helper for cycle detection func (g *Graph) hasCycleDFS(vertex, parent int, visited map[int]bool) bool { visited[vertex] = true for _, neighbor := range g.GetNeighbors(vertex) { if !visited[neighbor] { if g.hasCycleDFS(neighbor, vertex, visited) { return true } } else if neighbor != parent { // Found a back edge (cycle) return true } } return false } // ConnectedComponents finds all connected components func (g *Graph) ConnectedComponents() [][]int { visited := make(map[int]bool) components := [][]int{} for vertex := 0; vertex < g.vertices; vertex++ { if !visited[vertex] { component := []int{} g.dfsRecursive(vertex, visited, &component) components = append(components, component) } } return components } Complexity Analysis Time Complexity: O(V + E) Space Complexity: O(V) for recursion stack or explicit stack Practical Uses Pathfinding: Finding paths in mazes Topological Sorting: Ordering tasks with dependencies Cycle Detection: Detecting circular dependencies Component Analysis: Finding connected regions Game AI: Exploring game trees Example Usage func main() { g := NewGraph(7, false) g.AddEdge(0, 1) g.AddEdge(0, 2) g.AddEdge(1, 3) g.AddEdge(2, 4) g.AddEdge(3, 5) g.AddEdge(4, 5) // Vertex 6 is disconnected fmt.Println("DFS Recursive:", g.DFS(0)) fmt.Println("DFS Iterative:", g.DFSIterative(0)) components := g.ConnectedComponents() fmt.Printf("Connected components: %v\n", components) hasCycle := g.HasCycle() fmt.Printf("Has cycle: %v\n", hasCycle) } Dijkstra’s Algorithm Implementation package main import ( "container/heap" "fmt" "math" ) // PriorityQueueItem represents an item in the priority queue type PriorityQueueItem struct { vertex int distance int index int } // PriorityQueue implements heap.Interface type PriorityQueue []*PriorityQueueItem func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { return pq[i].distance < pq[j].distance } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = i pq[j].index = j } func (pq *PriorityQueue) Push(x interface{}) { n := len(*pq) item := x.(*PriorityQueueItem) item.index = n *pq = append(*pq, item) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] old[n-1] = nil item.index = -1 *pq = old[0 : n-1] return item } // Dijkstra finds shortest paths from source to all vertices func (wg *WeightedGraph) Dijkstra(source int) (map[int]int, map[int]int) { distances := make(map[int]int) parent := make(map[int]int) // Initialize distances for i := 0; i < wg.vertices; i++ { distances[i] = math.MaxInt32 parent[i] = -1 } distances[source] = 0 // Priority queue pq := make(PriorityQueue, 0) heap.Init(&pq) heap.Push(&pq, &PriorityQueueItem{vertex: source, distance: 0}) visited := make(map[int]bool) for pq.Len() > 0 { item := heap.Pop(&pq).(*PriorityQueueItem) vertex := item.vertex if visited[vertex] { continue } visited[vertex] = true // Explore neighbors for _, edge := range wg.GetEdges(vertex) { neighbor := edge.To newDist := distances[vertex] + edge.Weight if newDist < distances[neighbor] { distances[neighbor] = newDist parent[neighbor] = vertex heap.Push(&pq, &PriorityQueueItem{ vertex: neighbor, distance: newDist, }) } } } return distances, parent } // DijkstraPath finds the shortest path from source to target func (wg *WeightedGraph) DijkstraPath(source, target int) ([]int, int) { distances, parent := wg.Dijkstra(source) if distances[target] == math.MaxInt32 { return nil, -1 // No path exists } // Reconstruct path path := []int{} current := target for current != -1 { path = append([]int{current}, path...) current = parent[current] } return path, distances[target] } Complexity Analysis Time Complexity: O((V + E) log V) with binary heap Space Complexity: O(V) for distances and priority queue Practical Uses GPS Navigation: Finding shortest routes Network Routing: Packet routing (OSPF protocol) Social Networks: Finding degrees of separation Game Development: Pathfinding for NPCs Resource Allocation: Optimal resource distribution Example Usage func main() { wg := NewWeightedGraph(6, true) wg.AddEdge(0, 1, 4) wg.AddEdge(0, 2, 2) wg.AddEdge(1, 2, 1) wg.AddEdge(1, 3, 5) wg.AddEdge(2, 3, 8) wg.AddEdge(2, 4, 10) wg.AddEdge(3, 4, 2) wg.AddEdge(3, 5, 6) wg.AddEdge(4, 5, 3) distances, _ := wg.Dijkstra(0) fmt.Println("Shortest distances from vertex 0:") for vertex, dist := range distances { fmt.Printf(" Vertex %d: %d\n", vertex, dist) } path, dist := wg.DijkstraPath(0, 5) fmt.Printf("\nShortest path from 0 to 5: %v (distance: %d)\n", path, dist) } Bellman-Ford Algorithm Implementation package main import ( "fmt" "math" ) // BellmanFord finds shortest paths and detects negative cycles func (wg *WeightedGraph) BellmanFord(source int) (map[int]int, map[int]int, bool) { distances := make(map[int]int) parent := make(map[int]int) // Initialize distances for i := 0; i < wg.vertices; i++ { distances[i] = math.MaxInt32 parent[i] = -1 } distances[source] = 0 // Relax edges V-1 times for i := 0; i < wg.vertices-1; i++ { updated := false for vertex := 0; vertex < wg.vertices; vertex++ { if distances[vertex] == math.MaxInt32 { continue } for _, edge := range wg.GetEdges(vertex) { newDist := distances[vertex] + edge.Weight if newDist < distances[edge.To] { distances[edge.To] = newDist parent[edge.To] = vertex updated = true } } } // Early termination if no updates if !updated { break } } // Check for negative cycles hasNegativeCycle := false for vertex := 0; vertex < wg.vertices; vertex++ { if distances[vertex] == math.MaxInt32 { continue } for _, edge := range wg.GetEdges(vertex) { newDist := distances[vertex] + edge.Weight if newDist < distances[edge.To] { hasNegativeCycle = true break } } if hasNegativeCycle { break } } return distances, parent, hasNegativeCycle } // FindNegativeCycle finds a negative cycle if one exists func (wg *WeightedGraph) FindNegativeCycle() []int { distances := make(map[int]int) parent := make(map[int]int) // Initialize for i := 0; i < wg.vertices; i++ { distances[i] = 0 parent[i] = -1 } var cycleStart int = -1 // Relax edges V times for i := 0; i < wg.vertices; i++ { cycleStart = -1 for vertex := 0; vertex < wg.vertices; vertex++ { for _, edge := range wg.GetEdges(vertex) { newDist := distances[vertex] + edge.Weight if newDist < distances[edge.To] { distances[edge.To] = newDist parent[edge.To] = vertex cycleStart = edge.To } } } } if cycleStart == -1 { return nil // No negative cycle } // Find any vertex in the cycle for i := 0; i < wg.vertices; i++ { cycleStart = parent[cycleStart] } // Reconstruct cycle cycle := []int{} current := cycleStart for { cycle = append([]int{current}, cycle...) current = parent[current] if current == cycleStart { cycle = append([]int{current}, cycle...) break } } return cycle } Complexity Analysis Time Complexity: O(VE) Space Complexity: O(V) Practical Uses Currency Arbitrage: Detecting profit opportunities Network Analysis: Finding negative weight cycles Financial Modeling: Analyzing market inefficiencies Chemistry: Reaction pathway analysis Game Theory: Finding optimal strategies Example Usage func main() { wg := NewWeightedGraph(5, true) wg.AddEdge(0, 1, 5) wg.AddEdge(0, 2, 4) wg.AddEdge(1, 3, 3) wg.AddEdge(2, 1, 6) wg.AddEdge(3, 2, -2) distances, parent, hasNegCycle := wg.BellmanFord(0) if hasNegCycle { fmt.Println("Graph contains a negative cycle!") cycle := wg.FindNegativeCycle() fmt.Printf("Negative cycle: %v\n", cycle) } else { fmt.Println("Shortest distances from vertex 0:") for vertex, dist := range distances { fmt.Printf(" Vertex %d: %d\n", vertex, dist) } } } Floyd-Warshall Algorithm Implementation package main import ( "fmt" "math" ) // FloydWarshall finds shortest paths between all pairs of vertices func (wg *WeightedGraph) FloydWarshall() ([][]int, [][]int) { // Initialize distance matrix dist := make([][]int, wg.vertices) next := make([][]int, wg.vertices) for i := 0; i < wg.vertices; i++ { dist[i] = make([]int, wg.vertices) next[i] = make([]int, wg.vertices) for j := 0; j < wg.vertices; j++ { if i == j { dist[i][j] = 0 next[i][j] = j } else { dist[i][j] = math.MaxInt32 / 2 // Prevent overflow next[i][j] = -1 } } } // Fill in edge weights for vertex := 0; vertex < wg.vertices; vertex++ { for _, edge := range wg.GetEdges(vertex) { dist[vertex][edge.To] = edge.Weight next[vertex][edge.To] = edge.To } } // Floyd-Warshall algorithm for k := 0; k < wg.vertices; k++ { for i := 0; i < wg.vertices; i++ { for j := 0; j < wg.vertices; j++ { if dist[i][k]+dist[k][j] < dist[i][j] { dist[i][j] = dist[i][k] + dist[k][j] next[i][j] = next[i][k] } } } } return dist, next } // ReconstructPath reconstructs the path from source to target func ReconstructPath(next [][]int, source, target int) []int { if next[source][target] == -1 { return nil } path := []int{source} current := source for current != target { current = next[current][target] path = append(path, current) } return path } // HasNegativeCycle checks for negative cycles using Floyd-Warshall func HasNegativeCycleFloydWarshall(dist [][]int) bool { vertices := len(dist) for i := 0; i < vertices; i++ { if dist[i][i] < 0 { return true } } return false } // TransitiveClosure computes the transitive closure of a graph func (wg *WeightedGraph) TransitiveClosure() [][]bool { reach := make([][]bool, wg.vertices) // Initialize for i := 0; i < wg.vertices; i++ { reach[i] = make([]bool, wg.vertices) reach[i][i] = true } // Mark direct edges for vertex := 0; vertex < wg.vertices; vertex++ { for _, edge := range wg.GetEdges(vertex) { reach[vertex][edge.To] = true } } // Floyd-Warshall for reachability for k := 0; k < wg.vertices; k++ { for i := 0; i < wg.vertices; i++ { for j := 0; j < wg.vertices; j++ { reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]) } } } return reach } Complexity Analysis Time Complexity: O(V³) Space Complexity: O(V²) Practical Uses Network Analysis: Finding shortest paths between all nodes Graph Density: Computing transitive closure Reachability: Determining connectivity Routing Tables: Computing all-pairs shortest paths Relationship Analysis: Social network analysis Example Usage func main() { wg := NewWeightedGraph(4, true) wg.AddEdge(0, 1, 5) wg.AddEdge(0, 3, 10) wg.AddEdge(1, 2, 3) wg.AddEdge(2, 3, 1) dist, next := wg.FloydWarshall() fmt.Println("All-pairs shortest distances:") for i := 0; i < wg.vertices; i++ { for j := 0; j < wg.vertices; j++ { if dist[i][j] == math.MaxInt32/2 { fmt.Printf("INF ") } else { fmt.Printf("%3d ", dist[i][j]) } } fmt.Println() } fmt.Println("\nPath from 0 to 3:") path := ReconstructPath(next, 0, 3) fmt.Printf("%v (distance: %d)\n", path, dist[0][3]) // Transitive closure reach := wg.TransitiveClosure() fmt.Println("\nTransitive closure (reachability):") for i := 0; i < wg.vertices; i++ { for j := 0; j < wg.vertices; j++ { if reach[i][j] { fmt.Print("1 ") } else { fmt.Print("0 ") } } fmt.Println() } } Kruskal’s Algorithm (Minimum Spanning Tree) Implementation package main import ( "fmt" "sort" ) // DisjointSet implements Union-Find data structure type DisjointSet struct { parent []int rank []int } // NewDisjointSet creates a new disjoint set func NewDisjointSet(size int) *DisjointSet { ds := &DisjointSet{ parent: make([]int, size), rank: make([]int, size), } for i := 0; i < size; i++ { ds.parent[i] = i ds.rank[i] = 0 } return ds } // Find finds the representative of the set containing x func (ds *DisjointSet) Find(x int) int { if ds.parent[x] != x { ds.parent[x] = ds.Find(ds.parent[x]) // Path compression } return ds.parent[x] } // Union merges the sets containing x and y func (ds *DisjointSet) Union(x, y int) bool { rootX := ds.Find(x) rootY := ds.Find(y) if rootX == rootY { return false // Already in the same set } // Union by rank if ds.rank[rootX] < ds.rank[rootY] { ds.parent[rootX] = rootY } else if ds.rank[rootX] > ds.rank[rootY] { ds.parent[rootY] = rootX } else { ds.parent[rootY] = rootX ds.rank[rootX]++ } return true } // Kruskal finds the minimum spanning tree using Kruskal's algorithm func (wg *WeightedGraph) Kruskal() ([]Edge, int) { // Collect all edges edges := []Edge{} for vertex := 0; vertex < wg.vertices; vertex++ { for _, edge := range wg.GetEdges(vertex) { if !wg.directed || edge.From < edge.To { edges = append(edges, edge) } } } // Sort edges by weight sort.Slice(edges, func(i, j int) bool { return edges[i].Weight < edges[j].Weight }) // Initialize disjoint set ds := NewDisjointSet(wg.vertices) mst := []Edge{} totalWeight := 0 // Process edges in order for _, edge := range edges { if ds.Union(edge.From, edge.To) { mst = append(mst, edge) totalWeight += edge.Weight // MST has V-1 edges if len(mst) == wg.vertices-1 { break } } } return mst, totalWeight } Complexity Analysis Time Complexity: O(E log E) or O(E log V) Space Complexity: O(V) Practical Uses Network Design: Minimum cost network connections Circuit Design: Minimizing wire length Cluster Analysis: Finding hierarchical clusters Image Segmentation: Computer vision applications Approximate Solutions: TSP approximation Example Usage func main() { wg := NewWeightedGraph(6, false) wg.AddEdge(0, 1, 4) wg.AddEdge(0, 2, 4) wg.AddEdge(1, 2, 2) wg.AddEdge(1, 3, 5) wg.AddEdge(2, 3, 5) wg.AddEdge(2, 4, 1) wg.AddEdge(3, 4, 3) wg.AddEdge(3, 5, 7) wg.AddEdge(4, 5, 6) mst, totalWeight := wg.Kruskal() fmt.Println("Minimum Spanning Tree (Kruskal):") for _, edge := range mst { fmt.Printf(" %d -- %d (weight: %d)\n", edge.From, edge.To, edge.Weight) } fmt.Printf("Total weight: %d\n", totalWeight) } Prim’s Algorithm (Minimum Spanning Tree) Implementation package main import ( "container/heap" "fmt" "math" ) // MSTEdge represents an edge in the MST type MSTEdge struct { vertex int parent int weight int index int } // MSTHeap implements heap.Interface for Prim's algorithm type MSTHeap []*MSTEdge func (h MSTHeap) Len() int { return len(h) } func (h MSTHeap) Less(i, j int) bool { return h[i].weight < h[j].weight } func (h MSTHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] h[i].index = i h[j].index = j } func (h *MSTHeap) Push(x interface{}) { n := len(*h) edge := x.(*MSTEdge) edge.index = n *h = append(*h, edge) } func (h *MSTHeap) Pop() interface{} { old := *h n := len(old) edge := old[n-1] old[n-1] = nil edge.index = -1 *h = old[0 : n-1] return edge } // Prim finds the minimum spanning tree using Prim's algorithm func (wg *WeightedGraph) Prim(start int) ([]Edge, int) { inMST := make(map[int]bool) key := make(map[int]int) parent := make(map[int]int) // Initialize keys for i := 0; i < wg.vertices; i++ { key[i] = math.MaxInt32 parent[i] = -1 } key[start] = 0 // Priority queue pq := make(MSTHeap, 0) heap.Init(&pq) heap.Push(&pq, &MSTEdge{vertex: start, weight: 0}) mst := []Edge{} totalWeight := 0 for pq.Len() > 0 { edge := heap.Pop(&pq).(*MSTEdge) vertex := edge.vertex if inMST[vertex] { continue } inMST[vertex] = true if parent[vertex] != -1 { mst = append(mst, Edge{ From: parent[vertex], To: vertex, Weight: edge.weight, }) totalWeight += edge.weight } // Update neighbors for _, e := range wg.GetEdges(vertex) { if !inMST[e.To] && e.Weight < key[e.To] { key[e.To] = e.Weight parent[e.To] = vertex heap.Push(&pq, &MSTEdge{ vertex: e.To, parent: vertex, weight: e.Weight, }) } } } return mst, totalWeight } Complexity Analysis Time Complexity: O((V + E) log V) with binary heap Space Complexity: O(V) Practical Uses Network Design: Similar to Kruskal’s Cluster Analysis: Hierarchical clustering Approximation Algorithms: For NP-hard problems Broadcasting: Efficient message broadcasting Pipeline Design: Minimizing pipeline costs Example Usage func main() { wg := NewWeightedGraph(6, false) wg.AddEdge(0, 1, 4) wg.AddEdge(0, 2, 4) wg.AddEdge(1, 2, 2) wg.AddEdge(1, 3, 5) wg.AddEdge(2, 3, 5) wg.AddEdge(2, 4, 1) wg.AddEdge(3, 4, 3) wg.AddEdge(3, 5, 7) wg.AddEdge(4, 5, 6) mst, totalWeight := wg.Prim(0) fmt.Println("Minimum Spanning Tree (Prim):") for _, edge := range mst { fmt.Printf(" %d -- %d (weight: %d)\n", edge.From, edge.To, edge.Weight) } fmt.Printf("Total weight: %d\n", totalWeight) } Topological Sort Implementation package main import "fmt" // TopologicalSort performs topological sorting (DFS-based) func (g *Graph) TopologicalSort() []int { visited := make(map[int]bool) stack := []int{} // Visit all vertices for vertex := 0; vertex < g.vertices; vertex++ { if !visited[vertex] { g.topologicalSortDFS(vertex, visited, &stack) } } // Reverse the stack for i, j := 0, len(stack)-1; i < j; i, j = i+1, j-1 { stack[i], stack[j] = stack[j], stack[i] } return stack } // topologicalSortDFS is a helper for topological sort func (g *Graph) topologicalSortDFS(vertex int, visited map[int]bool, stack *[]int) { visited[vertex] = true for _, neighbor := range g.GetNeighbors(vertex) { if !visited[neighbor] { g.topologicalSortDFS(neighbor, visited, stack) } } *stack = append(*stack, vertex) } // TopologicalSortKahn performs topological sort using Kahn's algorithm (BFS-based) func (g *Graph) TopologicalSortKahn() ([]int, bool) { inDegree := make(map[int]int) // Calculate in-degrees for i := 0; i < g.vertices; i++ { inDegree[i] = 0 } for vertex := 0; vertex < g.vertices; vertex++ { for _, neighbor := range g.GetNeighbors(vertex) { inDegree[neighbor]++ } } // Queue for vertices with in-degree 0 queue := []int{} for vertex := 0; vertex < g.vertices; vertex++ { if inDegree[vertex] == 0 { queue = append(queue, vertex) } } result := []int{} for len(queue) > 0 { vertex := queue[0] queue = queue[1:] result = append(result, vertex) // Reduce in-degree of neighbors for _, neighbor := range g.GetNeighbors(vertex) { inDegree[neighbor]-- if inDegree[neighbor] == 0 { queue = append(queue, neighbor) } } } // Check if topological sort is possible (DAG) if len(result) != g.vertices { return nil, false // Graph has a cycle } return result, true } // HasCycleDirected detects cycles in directed graphs func (g *Graph) HasCycleDirected() bool { WHITE, GRAY, BLACK := 0, 1, 2 color := make(map[int]int) for i := 0; i < g.vertices; i++ { color[i] = WHITE } for vertex := 0; vertex < g.vertices; vertex++ { if color[vertex] == WHITE { if g.hasCycleDirectedDFS(vertex, color) { return true } } } return false } // hasCycleDirectedDFS is a helper for cycle detection in directed graphs func (g *Graph) hasCycleDirectedDFS(vertex int, color map[int]int) bool { color[vertex] = 1 // GRAY for _, neighbor := range g.GetNeighbors(vertex) { if color[neighbor] == 1 { // GRAY - back edge found return true } if color[neighbor] == 0 && g.hasCycleDirectedDFS(neighbor, color) { return true } } color[vertex] = 2 // BLACK return false } Complexity Analysis Time Complexity: O(V + E) Space Complexity: O(V) Practical Uses Build Systems: Dependency resolution (makefiles) Task Scheduling: Ordering tasks with dependencies Course Prerequisites: Academic planning Spreadsheet Formulas: Cell calculation order Package Management: Install order determination Example Usage func main() { // Create a DAG (Directed Acyclic Graph) g := NewGraph(6, true) g.AddEdge(5, 2) g.AddEdge(5, 0) g.AddEdge(4, 0) g.AddEdge(4, 1) g.AddEdge(2, 3) g.AddEdge(3, 1) // DFS-based topological sort dfsOrder := g.TopologicalSort() fmt.Println("Topological Sort (DFS):", dfsOrder) // Kahn's algorithm kahnOrder, isDAG := g.TopologicalSortKahn() if isDAG { fmt.Println("Topological Sort (Kahn):", kahnOrder) } else { fmt.Println("Graph has a cycle!") } // Check for cycles hasCycle := g.HasCycleDirected() fmt.Printf("Has cycle: %v\n", hasCycle) } Advanced Algorithms Strongly Connected Components (Kosaraju’s Algorithm) // StronglyConnectedComponents finds SCCs using Kosaraju's algorithm func (g *Graph) StronglyConnectedComponents() [][]int { // Step 1: Fill order of vertices (finishing times) visited := make(map[int]bool) stack := []int{} for vertex := 0; vertex < g.vertices; vertex++ { if !visited[vertex] { g.fillOrder(vertex, visited, &stack) } } // Step 2: Create transpose graph transpose := g.GetTranspose() // Step 3: Process vertices in reverse finishing order visited = make(map[int]bool) sccs := [][]int{} for len(stack) > 0 { vertex := stack[len(stack)-1] stack = stack[:len(stack)-1] if !visited[vertex] { scc := []int{} transpose.dfsRecursive(vertex, visited, &scc) sccs = append(sccs, scc) } } return sccs } // fillOrder is a helper to fill the stack with finishing times func (g *Graph) fillOrder(vertex int, visited map[int]bool, stack *[]int) { visited[vertex] = true for _, neighbor := range g.GetNeighbors(vertex) { if !visited[neighbor] { g.fillOrder(neighbor, visited, stack) } } *stack = append(*stack, vertex) } // GetTranspose returns the transpose of the graph func (g *Graph) GetTranspose() *Graph { transpose := NewGraph(g.vertices, true) for vertex := 0; vertex < g.vertices; vertex++ { for _, neighbor := range g.GetNeighbors(vertex) { transpose.AddEdge(neighbor, vertex) } } return transpose } A* Search Algorithm // AStarNode represents a node in A* search type AStarNode struct { vertex int gScore int // Cost from start fScore int // gScore + heuristic index int } // AStarHeap implements heap for A* type AStarHeap []*AStarNode func (h AStarHeap) Len() int { return len(h) } func (h AStarHeap) Less(i, j int) bool { return h[i].fScore < h[j].fScore } func (h AStarHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] h[i].index = i h[j].index = j } func (h *AStarHeap) Push(x interface{}) { n := len(*h) node := x.(*AStarNode) node.index = n *h = append(*h, node) } func (h *AStarHeap) Pop() interface{} { old := *h n := len(old) node := old[n-1] old[n-1] = nil node.index = -1 *h = old[0 : n-1] return node } // AStar finds the shortest path using A* algorithm func (wg *WeightedGraph) AStar(start, goal int, heuristic func(int, int) int) ([]int, int) { gScore := make(map[int]int) parent := make(map[int]int) for i := 0; i < wg.vertices; i++ { gScore[i] = math.MaxInt32 parent[i] = -1 } gScore[start] = 0 pq := make(AStarHeap, 0) heap.Init(&pq) heap.Push(&pq, &AStarNode{ vertex: start, gScore: 0, fScore: heuristic(start, goal), }) visited := make(map[int]bool) for pq.Len() > 0 { current := heap.Pop(&pq).(*AStarNode) if current.vertex == goal { // Reconstruct path path := []int{} v := goal for v != -1 { path = append([]int{v}, path...) v = parent[v] } return path, gScore[goal] } if visited[current.vertex] { continue } visited[current.vertex] = true for _, edge := range wg.GetEdges(current.vertex) { tentativeG := gScore[current.vertex] + edge.Weight if tentativeG < gScore[edge.To] { parent[edge.To] = current.vertex gScore[edge.To] = tentativeG fScore := tentativeG + heuristic(edge.To, goal) heap.Push(&pq, &AStarNode{ vertex: edge.To, gScore: tentativeG, fScore: fScore, }) } } } return nil, -1 // No path found } Bipartite Graph Detection // IsBipartite checks if the graph is bipartite func (g *Graph) IsBipartite() (bool, map[int]int) { color := make(map[int]int) for i := 0; i < g.vertices; i++ { color[i] = -1 } for vertex := 0; vertex < g.vertices; vertex++ { if color[vertex] == -1 { if !g.isBipartiteBFS(vertex, color) { return false, nil } } } return true, color } // isBipartiteBFS uses BFS to check bipartiteness func (g *Graph) isBipartiteBFS(start int, color map[int]int) bool { queue := []int{start} color[start] = 0 for len(queue) > 0 { vertex := queue[0] queue = queue[1:] for _, neighbor := range g.GetNeighbors(vertex) { if color[neighbor] == -1 { color[neighbor] = 1 - color[vertex] queue = append(queue, neighbor) } else if color[neighbor] == color[vertex] { return false } } } return true } Performance Comparison Time Complexity Summary Algorithm Time Complexity Space Complexity Use Case BFS O(V + E) O(V) Shortest path (unweighted) DFS O(V + E) O(V) Path finding, cycle detection Dijkstra O((V + E) log V) O(V) Shortest path (positive weights) Bellman-Ford O(VE) O(V) Negative weights, cycle detection Floyd-Warshall O(V³) O(V²) All-pairs shortest paths Kruskal O(E log E) O(V) MST for sparse graphs Prim O((V + E) log V) O(V) MST for dense graphs Topological Sort O(V + E) O(V) Dependency resolution A* O(E log V) O(V) Optimal pathfinding Best Practices Choose the Right Algorithm: Match algorithm to problem constraints Graph Representation: Use adjacency list for sparse graphs, matrix for dense Edge Cases: Handle disconnected components, self-loops, cycles Negative Weights: Use Bellman-Ford, not Dijkstra Memory Efficiency: Consider space-time tradeoffs Testing: Test with various graph types (complete, sparse, DAG, etc.) Optimization: Use appropriate data structures (heap, disjoint set) Common Pitfalls Wrong Algorithm: Using Dijkstra with negative weights Infinite Loops: Not handling cycles properly Memory Issues: Dense graphs with adjacency matrix Integer Overflow: Not handling large weights Directed vs Undirected: Mixing up graph types Disconnected Graphs: Forgetting to handle multiple components Practical Applications Social Networks Friend Recommendations: BFS for finding mutual friends Influence Spread: DFS for viral propagation Community Detection: Connected components Navigation Systems Route Planning: Dijkstra’s or A* for GPS Traffic Optimization: Real-time graph updates Multi-destination: Traveling salesman approximations Network Infrastructure Network Design: MST for minimum cost Routing Protocols: Shortest path algorithms Fault Tolerance: Finding alternative paths Dependency Management Build Systems: Topological sort for compilation order Package Managers: Dependency resolution Task Scheduling: DAG-based scheduling Game Development Pathfinding: A* for NPC movement Game Trees: DFS for decision trees Quest Dependencies: Topological ordering Complete Example: Graph Library package main import ( "container/heap" "fmt" "math" ) // GraphLib provides a comprehensive graph algorithm library type GraphLib struct { graph *WeightedGraph } // NewGraphLib creates a new graph library instance func NewGraphLib(vertices int, directed bool) *GraphLib { return &GraphLib{ graph: NewWeightedGraph(vertices, directed), } } // ShortestPath finds the shortest path between two vertices func (gl *GraphLib) ShortestPath(from, to int, algorithm string) ([]int, int) { switch algorithm { case "dijkstra": return gl.graph.DijkstraPath(from, to) case "bellman-ford": distances, parent, _ := gl.graph.BellmanFord(from) if distances[to] == math.MaxInt32 { return nil, -1 } path := gl.reconstructPath(parent, from, to) return path, distances[to] default: return gl.graph.DijkstraPath(from, to) } } // reconstructPath reconstructs path from parent map func (gl *GraphLib) reconstructPath(parent map[int]int, from, to int) []int { path := []int{} current := to for current != -1 { path = append([]int{current}, path...) if current == from { break } current = parent[current] } return path } // MinimumSpanningTree finds MST using specified algorithm func (gl *GraphLib) MinimumSpanningTree(algorithm string) ([]Edge, int) { switch algorithm { case "kruskal": return gl.graph.Kruskal() case "prim": return gl.graph.Prim(0) default: return gl.graph.Kruskal() } } func main() { // Create graph library lib := NewGraphLib(6, true) // Add edges lib.graph.AddEdge(0, 1, 4) lib.graph.AddEdge(0, 2, 2) lib.graph.AddEdge(1, 2, 1) lib.graph.AddEdge(1, 3, 5) lib.graph.AddEdge(2, 3, 8) lib.graph.AddEdge(3, 4, 6) // Find shortest path path, dist := lib.ShortestPath(0, 4, "dijkstra") fmt.Printf("Shortest path: %v (distance: %d)\n", path, dist) // Find MST mst, weight := lib.MinimumSpanningTree("kruskal") fmt.Printf("MST weight: %d\n", weight) for _, edge := range mst { fmt.Printf(" %d -> %d (weight: %d)\n", edge.From, edge.To, edge.Weight) } } Conclusion Graph algorithms are essential tools for solving complex problems in computer science. This guide covered: ...