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:
...