14. Graphs

📋 Jump to Takeaways

Graphs model relationships. Social networks (people connected by friendships), maps (cities connected by roads), dependencies (tasks that must happen before other tasks), the internet (pages connected by links). Any time you have "things" and "connections between things," you have a graph.

The Structure

A graph has vertices (nodes) and edges (connections). Edges can be:

Directed — one-way (A → B doesn't mean B → A)
Undirected — two-way (A — B means both can reach each other)
Weighted — edges have costs (road distances, network latency)
Unweighted — all edges are equal

Undirected:          Directed:           Weighted:
  A — B              A → B              A —3— B
  |   |              ↓   ↓              |     |
  C — D              C → D              2     5
                                        |     |
                                        C —1— D

Representation

Two standard ways to store a graph:

Adjacency list — each node stores its neighbors. Best for sparse graphs (few edges relative to nodes).

// Adjacency list — map of node → neighbors
graph := map[int][]int{
    0: {1, 2},
    1: {0, 3},
    2: {0, 3},
    3: {1, 2},
}

// Weighted adjacency list
type Edge struct {
    To, Weight int
}
weighted := map[int][]Edge{
    0: {{1, 3}, {2, 2}},
    1: {{3, 5}},
    2: {{3, 1}},
}

Adjacency matrix — 2D array where matrix[i][j] = 1 means edge from i to j. Best for dense graphs or when you need O(1) edge lookup.

// Adjacency matrix — O(1) edge check, O(V²) space
matrix := [][]bool{
    {false, true, true, false},  // node 0 connects to 1, 2
    {true, false, false, true},  // node 1 connects to 0, 3
    {true, false, false, true},  // node 2 connects to 0, 3
    {false, true, true, false},  // node 3 connects to 1, 2
}

	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Check edge exists	O(degree)	O(1)
Find all neighbors	O(degree)	O(V)
Best for	Sparse graphs	Dense graphs

Most interview problems use adjacency lists.

DFS — Depth-First Search

Go as deep as possible before backtracking. Uses a stack (or recursion).

// DFS — recursive (passing state explicitly)
func dfs(graph map[int][]int, node int, visited map[int]bool, order *[]int) {
    visited[node] = true
    *order = append(*order, node)
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            dfs(graph, neighbor, visited, order)
        }
    }
}

// DFS — recursive with closure (cleaner call site)
func dfsWithClosure(graph map[int][]int, start int) []int {
    visited := map[int]bool{}
    order := []int{}

    var dfs func(node int)
    dfs = func(node int) {
        visited[node] = true
        order = append(order, node)
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                dfs(neighbor)
            }
        }
    }

    dfs(start)
    return order
}

The closure version captures visited and order from the enclosing scope — no need to pass them on every recursive call. This is the idiomatic Go pattern for graph DFS.

// DFS — iterative with explicit stack
func dfsIterative(graph map[int][]int, start int) []int {
    visited := map[int]bool{}
    stack := []int{start}
    order := []int{}
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if visited[node] {
            continue
        }
        visited[node] = true
        order = append(order, node)
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                stack = append(stack, neighbor)
            }
        }
    }
    return order
}

DFS explores one path completely before trying another. Good for: detecting cycles, topological sort, finding connected components, path existence.

BFS — Breadth-First Search

Explore all neighbors at distance 1, then distance 2, then distance 3. Uses a queue.

// BFS — finds shortest path in unweighted graphs
func bfs(graph map[int][]int, start int) map[int]int {
    dist := map[int]int{start: 0}
    queue := []int{start}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        for _, neighbor := range graph[node] {
            if _, ok := dist[neighbor]; !ok {
                dist[neighbor] = dist[node] + 1
                queue = append(queue, neighbor)
            }
        }
    }
    return dist // distance from start to every reachable node
}

BFS guarantees shortest path in unweighted graphs. The first time you reach a node is the shortest way to get there.

Note: We use a slice as a queue (queue[1:] to dequeue). Go has no built-in deque — slices are the standard choice for BFS. The underlying array doesn't shrink, but for bounded problems (at most O(V) elements) the memory is freed when the function returns. For long-lived queues with millions of operations, this leaks. For BFS in interview problems (short-lived queues), it's fine. In production, use a ring buffer or track an index. See Stacks and Queues for the full tradeoff.

Multi-Source BFS

Sometimes you start BFS from multiple sources simultaneously. Instead of running BFS from each source separately (which would be O(V × (V+E))), you enqueue ALL sources at once and expand outward in parallel.

LeetCode 994 - Rotting Oranges

// Rotting oranges: how many minutes until all oranges rot?
// Start BFS from ALL rotten oranges at once
func orangesRotting(grid [][]int) int {
    queue := [][]int{}
    fresh := 0
    for i := range grid {
        for j := range grid[0] {
            if grid[i][j] == 2 {
                queue = append(queue, []int{i, j})
            } else if grid[i][j] == 1 {
                fresh++
            }
        }
    }
    minutes := 0
    dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
    for len(queue) > 0 && fresh > 0 {
        size := len(queue)
        for k := 0; k < size; k++ {
            cell := queue[0]
            queue = queue[1:]
            for _, d := range dirs {
                r, c := cell[0]+d[0], cell[1]+d[1]
                if r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0]) && grid[r][c] == 1 {
                    grid[r][c] = 2
                    fresh--
                    queue = append(queue, []int{r, c})
                }
            }
        }
        minutes++
    }
    if fresh > 0 {
        return -1
    }
    return minutes
}

The key insight: by starting from all sources at once, each cell gets the minimum distance to its nearest source. One BFS pass, O(V+E) total.

Topological Sort

Topological sort orders nodes in a directed acyclic graph (DAG) so that for every edge A → B, A comes before B. Think: course prerequisites, build dependencies, task scheduling.

Kahn's Algorithm (BFS-based):

Count in-degrees (how many edges point to each node)
Enqueue all nodes with in-degree 0 (no dependencies)
Process queue: for each node, reduce in-degree of its neighbors. If a neighbor hits 0, enqueue it.

LeetCode 210 - Course Schedule II

func topologicalSort(n int, edges [][]int) []int {
    graph := make([][]int, n)
    inDegree := make([]int, n)
    for _, e := range edges {
        pre, crs := e[0], e[1]
        graph[pre] = append(graph[pre], crs)
        inDegree[crs]++
    }

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

    var order []int
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)
        for _, neighbor := range graph[node] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }
    if len(order) != n {
        return nil // cycle detected — not a DAG
    }
    return order
}

If the result has fewer nodes than the graph, there's a cycle — topological sort is impossible. This is also how you detect cycles in directed graphs.

When DFS vs BFS

Use DFS when	Use BFS when
Detecting cycles	Finding shortest path (unweighted)
Topological sort	Level-order processing
Path existence (any path)	Nearest neighbor queries
Exploring all possibilities	Minimum steps/moves
Space is tight (recursion stack)	You need the closest result first

Rule of thumb: if the problem says "minimum," "shortest," or "fewest," think BFS. If it says "all paths," "detect cycle," or "can you reach," think DFS.

Common Graph Problems

Connected components — how many separate groups exist? Run DFS/BFS from each unvisited node, count how many times you start.

LeetCode 323 - Number of Connected Components in an Undirected Graph

func countComponents(n int, graph map[int][]int) int {
    visited := make([]bool, n)
    count := 0

    var explore func(node int)
    explore = func(node int) {
        visited[node] = true
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                explore(neighbor)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            explore(i)
            count++
        }
    }
    return count
}

Cycle detection — in a directed graph, if DFS visits a node that's currently on the recursion stack, there's a cycle.

Topological sort — order tasks so dependencies come first. Only works on directed acyclic graphs (DAGs). Use DFS with post-order, or BFS with in-degree counting (Kahn's algorithm).

Grid as graph — many problems give you a 2D grid. Each cell is a node, adjacent cells (up/down/left/right) are edges.

LeetCode 200 - Number of Islands

Given a 2D grid of '1's (land) and '0's (water), count the number of islands.

// Number of islands — DFS on a grid
func numIslands(grid [][]byte) int {
    count := 0
    for i := range grid {
        for j := range grid[0] {
            if grid[i][j] == '1' {
                dfsGrid(grid, i, j) // sink the island
                count++
            }
        }
    }
    return count
}

func dfsGrid(grid [][]byte, i, j int) {
    if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == '0' {
        return
    }
    grid[i][j] = '0' // mark visited
    dfsGrid(grid, i+1, j)
    dfsGrid(grid, i-1, j)
    dfsGrid(grid, i, j+1)
    dfsGrid(grid, i, j-1)
}

Complexity

Algorithm	Time	Space
DFS	O(V + E)	O(V)
BFS	O(V + E)	O(V)
Topological sort	O(V + E)	O(V)

V = vertices, E = edges. Both DFS and BFS visit every node and every edge exactly once.

Practice Problems

Problem	Difficulty	Link
Flood Fill	Easy	LeetCode 733
Number of Islands	Medium	LeetCode 200
All Paths From Source to Target	Medium	LeetCode 797
Clone Graph	Medium	LeetCode 133
Course Schedule	Medium	LeetCode 207
Course Schedule II	Medium	LeetCode 210
Pacific Atlantic Water Flow	Medium	LeetCode 417
Word Ladder	Hard	LeetCode 127
Rotting Oranges	Medium	LeetCode 994

Key Takeaways

Graphs model relationships — vertices are things, edges are connections
Adjacency lists for sparse graphs (most problems), matrices for dense graphs
DFS goes deep first (stack/recursion) — cycles, topological sort, path existence
BFS goes wide first (queue) — shortest path in unweighted graphs, minimum steps
"Minimum/shortest/fewest" → BFS. "All paths/cycle/reachability" → DFS
Grids are graphs — each cell connects to its 4 (or 8) neighbors
Both DFS and BFS are O(V + E) time