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

Friend Recommendations: BFS for finding mutual friends
Influence Spread: DFS for viral propagation
Community Detection: Connected components

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:

Traversal Algorithms: BFS and DFS for exploring graphs
Shortest Path: Dijkstra’s, Bellman-Ford, Floyd-Warshall, and A*
Minimum Spanning Trees: Kruskal’s and Prim’s algorithms
DAG Algorithms: Topological sorting and cycle detection
Advanced Topics: SCCs, bipartite detection, and more

Each algorithm has specific use cases, complexity characteristics, and implementation considerations. Choose the right algorithm based on your graph properties and problem requirements.

Key Takeaways:

Understand time/space complexity tradeoffs
Match algorithms to problem constraints
Use appropriate data structures
Handle edge cases properly
Test thoroughly with various graph types

Master these algorithms to build efficient solutions for graph-based problems in your Go applications.

Introduction#

Graph Representation#

Adjacency List#

Weighted Graph#

Breadth-First Search (BFS)#

Implementation#

Complexity Analysis#

Practical Uses#

Example Usage#

Depth-First Search (DFS)#

Implementation#

Complexity Analysis#

Practical Uses#

Example Usage#

Dijkstra’s Algorithm#

Implementation#

Complexity Analysis#

Practical Uses#

Example Usage#

Bellman-Ford Algorithm#

Implementation#

Complexity Analysis#

Practical Uses#

Example Usage#

Floyd-Warshall Algorithm#

Implementation#

Complexity Analysis#

Practical Uses#

Example Usage#

Kruskal’s Algorithm (Minimum Spanning Tree)#

Implementation#

Complexity Analysis#

Practical Uses#

Example Usage#

Prim’s Algorithm (Minimum Spanning Tree)#

Implementation#

Complexity Analysis#

Practical Uses#

Example Usage#

Topological Sort#

Implementation#

Complexity Analysis#

Practical Uses#

Example Usage#

Advanced Algorithms#

Strongly Connected Components (Kosaraju’s Algorithm)#

A* Search Algorithm#

Bipartite Graph Detection#

Performance Comparison#

Time Complexity Summary#

Best Practices#

Common Pitfalls#

Practical Applications#

Social Networks#

Navigation Systems#

Network Infrastructure#

Dependency Management#

Game Development#

Complete Example: Graph Library#

Conclusion#

Introduction

Graph Representation

Adjacency List

Weighted Graph

Breadth-First Search (BFS)

Implementation

Complexity Analysis

Practical Uses

Example Usage

Depth-First Search (DFS)

Implementation

Complexity Analysis

Practical Uses

Example Usage

Dijkstra’s Algorithm

Implementation

Complexity Analysis

Practical Uses

Example Usage

Bellman-Ford Algorithm

Implementation

Complexity Analysis

Practical Uses

Example Usage

Floyd-Warshall Algorithm

Implementation

Complexity Analysis

Practical Uses

Example Usage

Kruskal’s Algorithm (Minimum Spanning Tree)

Implementation

Complexity Analysis

Practical Uses

Example Usage

Prim’s Algorithm (Minimum Spanning Tree)

Implementation

Complexity Analysis

Practical Uses

Example Usage

Topological Sort

Implementation

Complexity Analysis

Practical Uses

Example Usage

Advanced Algorithms

Strongly Connected Components (Kosaraju’s Algorithm)

A* Search Algorithm

Bipartite Graph Detection

Performance Comparison

Time Complexity Summary

Best Practices

Common Pitfalls

Practical Applications

Social Networks

Navigation Systems

Network Infrastructure

Dependency Management

Game Development

Complete Example: Graph Library

Conclusion