Data Structures, Algorithms and Programming Patterns · Part 5 of 9

Data Structures and Algorithms, Part 5: Graphs and How to Walk Them

Maps, friend networks, course prerequisites and game boards all look different, yet they share one shape: things connected to other things. That shape is a graph. In this part you learn how to store one, how to walk it in two different ways, and how a handful of short algorithms answer questions about paths, groups and order.

1. What a graph is, and what it models

A graph is a set of things and the connections between them. The things are called vertices (or nodes; one is a vertex). The connections are called edges. That is the whole definition. A graph is just dots and lines.

It sounds too simple to be useful, but a huge number of real problems are graphs in disguise:

• A road map. Towns are vertices, roads are edges.
• A friends network. People are vertices, friendships are edges.
• Course prerequisites. Courses are vertices, “take this before that” is an edge.
• The web. Pages are vertices, links are edges.
• A maze or a game board. Cells are vertices, legal moves are edges.

The words you need

• Undirected edge: works both ways, like a friendship. Directed edge: works one way, like “follows” or “is a prerequisite of”. We draw it as an arrow.
• Weighted edge: has a number on it, such as a distance or a cost. An unweighted graph treats every edge as equal.
• Neighbours of a vertex are the vertices it shares an edge with. The degree of a vertex is how many edges touch it. (For directed graphs we split this into in-degree, arrows coming in, and out-degree, arrows going out.)
• A path is a walk along edges from one vertex to another. Its length is the number of edges.
• A cycle is a path that starts and ends at the same vertex.
• A graph is connected if there is a path between every pair of vertices. If not, it falls into separate pieces, and each piece is a connected component.
• A DAG is a directed acyclic graph: arrows only, and no cycles. Course prerequisites should always form a DAG.

In the rest of this part, V means the number of vertices and E means the number of edges. Almost every cost below is written in terms of those two numbers.

2. How to store a graph

Before we can walk a graph, the computer needs to hold it in memory. There are three common ways. Each answers the question “who are the neighbours of vertex u?” at a different price.

1. Adjacency list

For every vertex, keep a list of its neighbours. In Kotlin that is an Array<MutableList<Int>> when vertices are numbered 0 until n, or a Map<Int, List<Int>> when vertex ids are arbitrary (names, big numbers). This is the default choice.

2. Adjacency matrix

A square table with one row and one column per vertex. Cell [u][v] says whether an edge from u to v exists (or stores its weight). Checking one specific edge is instant, but the table has V × V cells even if the graph has almost no edges.

3. Edge list

Just a list of pairs, like (0, 1), (0, 2). It is the simplest form and it is how data often arrives. It is awkward for walking, so we usually convert it to an adjacency list first. Some algorithms (like Kruskal's, later) want exactly this form.

A graph is sparse when E is much smaller than V², which is true for road maps and friend networks. That is why the list wins most of the time.

fun main() {
    val n = 4
    val edges = listOf(0 to 1, 0 to 2, 1 to 3, 2 to 3)

    // Adjacency list (undirected: store each edge in both directions)
    val adj = Array(n) { mutableListOf<Int>() }
    for ((a, b) in edges) {
        adj[a].add(b)
        adj[b].add(a)
    }
    for (u in 0 until n) println("$u: ${adj[u]}")

    // Adjacency matrix
    val matrix = Array(n) { BooleanArray(n) }
    for ((a, b) in edges) {
        matrix[a][b] = true
        matrix[b][a] = true
    }
    println("edge 1-3 exists? ${matrix[1][3]}")
    println("edge 0-3 exists? ${matrix[0][3]}")

    // Names as vertices: a Map works when ids are not 0..n-1
    val friends = mapOf(
        "Ana" to listOf("Ben", "Cy"),
        "Ben" to listOf("Ana"),
        "Cy" to listOf("Ana")
    )
    println("Ana's friends: ${friends["Ana"]}")
    println("Zed's friends: ${friends["Zed"] ?: emptyList()}")
}

3. Breadth-first search: explore in rings

Walking a graph means visiting vertices by following edges. The two classic ways differ in which vertex you visit next. We start with breadth-first search, or BFS.

To do this we need a queue (Part 3): first in, first out. The recipe:

1. Put the start vertex in the queue and mark it visited.
2. Take the vertex at the front of the queue.
3. For each neighbour that is not yet visited: mark it visited and add it to the back of the queue.
4. Repeat from step 2 until the queue is empty.

The visited marks matter. Without them, a graph with a cycle would make us walk around it forever.

Shortest path in an unweighted graph

Here is the useful fact. Because BFS visits vertices closest first, the first time it reaches a vertex is along a path with the fewest edges. So BFS gives you the shortest path for free, as long as every edge counts the same. We record two things for each vertex: its dist (edges from the start) and its parent (who we came from), so we can rebuild the route backwards.

fun bfs(adj: Array<MutableList<Int>>, start: Int): Pair<IntArray, IntArray> {
    val dist = IntArray(adj.size) { -1 }     // -1 means "not reached yet"
    val parent = IntArray(adj.size) { -1 }
    val queue = ArrayDeque<Int>()
    dist[start] = 0
    queue.addLast(start)
    while (queue.isNotEmpty()) {
        val u = queue.removeFirst()
        for (v in adj[u]) {
            if (dist[v] == -1) {             // not visited
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.addLast(v)
            }
        }
    }
    return dist to parent
}

fun pathTo(parent: IntArray, dist: IntArray, target: Int): List<Int> {
    if (dist[target] == -1) return emptyList()   // unreachable
    val path = ArrayList<Int>()
    var cur = target
    while (cur != -1) {
        path.add(cur)
        cur = parent[cur]
    }
    path.reverse()
    return path
}

fun main() {
    val n = 8   // vertex 7 is alone: the graph is disconnected
    val edges = listOf(0 to 1, 0 to 2, 1 to 3, 2 to 4, 2 to 5, 3 to 6)
    val adj = Array(n) { mutableListOf<Int>() }
    for ((a, b) in edges) { adj[a].add(b); adj[b].add(a) }

    val (dist, parent) = bfs(adj, 0)
    println("distances from 0: ${dist.toList()}")
    println("path 0 -> 6: ${pathTo(parent, dist, 6)}")
    println("path 0 -> 5: ${pathTo(parent, dist, 5)}")
    println("path 0 -> 7: ${pathTo(parent, dist, 7)}   (unreachable)")
}

Cost. Each vertex enters the queue at most once, and each edge is looked at once (twice in an undirected graph). That is O(V + E) time and O(V) extra space for the queue and the arrays.

4. Depth-first search: go deep, then back up

Depth-first search, or DFS, picks a different order. It follows one path as far as it can go, and only when it is stuck does it back up and try another branch.

The natural way to write it is recursion: a function that calls itself for each unvisited neighbour. The call stack remembers where to back up to. You can also write it with an explicit stack (Part 3) instead. It is the same idea as BFS with the queue swapped for a stack.

// Recursive DFS: the call stack remembers where to back up to.
fun dfsRecursive(adj: Array<MutableList<Int>>, u: Int, visited: BooleanArray, order: MutableList<Int>) {
    visited[u] = true
    order.add(u)
    for (v in adj[u]) {
        if (!visited[v]) dfsRecursive(adj, v, visited, order)
    }
}

// Iterative DFS: same idea with our own stack.
fun dfsIterative(adj: Array<MutableList<Int>>, start: Int): List<Int> {
    val visited = BooleanArray(adj.size)
    val order = ArrayList<Int>()
    val stack = ArrayDeque<Int>()
    stack.addLast(start)
    while (stack.isNotEmpty()) {
        val u = stack.removeLast()
        if (visited[u]) continue
        visited[u] = true
        order.add(u)
        for (v in adj[u]) if (!visited[v]) stack.addLast(v)
    }
    return order
}

// Connected components: start a new DFS from every vertex we have not seen.
fun countComponents(adj: Array<MutableList<Int>>): Int {
    val visited = BooleanArray(adj.size)
    var count = 0
    for (u in adj.indices) {
        if (!visited[u]) {
            count++
            dfsRecursive(adj, u, visited, ArrayList())
        }
    }
    return count
}

// Cycle in an undirected graph: meeting an already-visited vertex
// that is not the one we just came from means we closed a loop.
fun hasCycle(adj: Array<MutableList<Int>>): Boolean {
    val visited = BooleanArray(adj.size)
    fun go(u: Int, from: Int): Boolean {
        visited[u] = true
        for (v in adj[u]) {
            if (!visited[v]) {
                if (go(v, u)) return true
            } else if (v != from) {
                return true
            }
        }
        return false
    }
    for (u in adj.indices) {
        if (!visited[u] && go(u, -1)) return true
    }
    return false
}

fun build(n: Int, edges: List<Pair<Int, Int>>): Array<MutableList<Int>> {
    val adj = Array(n) { mutableListOf<Int>() }
    for ((a, b) in edges) { adj[a].add(b); adj[b].add(a) }
    return adj
}

fun main() {
    val tree = build(6, listOf(0 to 1, 0 to 2, 1 to 3, 2 to 4, 2 to 5))
    val order = ArrayList<Int>()
    dfsRecursive(tree, 0, BooleanArray(6), order)
    println("recursive order: $order")
    println("iterative order: ${dfsIterative(tree, 0)}")
    println("components in tree: ${countComponents(tree)}")
    println("tree has cycle? ${hasCycle(tree)}")

    val loop = build(5, listOf(0 to 1, 1 to 2, 2 to 0, 3 to 4))
    println("components in loop graph: ${countComponents(loop)}")
    println("loop graph has cycle? ${hasCycle(loop)}")
}

Cost. Like BFS, DFS touches each vertex and edge a constant number of times: O(V + E) time. The extra space is the visited array plus the recursion depth, which can reach O(V) on a long chain.

5. Grids are graphs too

A maze, a chessboard, a photo and a game map are all grids. A grid is a graph in disguise: each cell is a vertex, and it has an edge to the cells next to it. Most problems use four directions (up, down, left, right). We do not build an adjacency list. We compute the neighbours on the spot with a list of direction steps.

The classic exercise is flood fill: stand on one land cell, then spread to every connected land cell, marking each as seen (like paint spreading in an image editor). Run it from each unseen land cell, and the number of runs is the number of islands. Always check the bounds before you touch a cell.

val dr = intArrayOf(-1, 1, 0, 0)   // row change for up, down, left, right
val dc = intArrayOf(0, 0, -1, 1)   // column change

fun countIslands(grid: List<String>): Int {
    if (grid.isEmpty()) return 0
    val rows = grid.size
    val cols = grid[0].length
    val seen = Array(rows) { BooleanArray(cols) }
    var islands = 0

    for (r in 0 until rows) {
        for (c in 0 until cols) {
            if (grid[r][c] == '1' && !seen[r][c]) {
                islands++
                // flood fill from (r, c) with a stack
                val stack = ArrayDeque<Pair<Int, Int>>()
                seen[r][c] = true
                stack.addLast(r to c)
                while (stack.isNotEmpty()) {
                    val (cr, cc) = stack.removeLast()
                    for (d in 0 until 4) {
                        val nr = cr + dr[d]
                        val nc = cc + dc[d]
                        val inside = nr in 0 until rows && nc in 0 until cols
                        if (inside && grid[nr][nc] == '1' && !seen[nr][nc]) {
                            seen[nr][nc] = true
                            stack.addLast(nr to nc)
                        }
                    }
                }
            }
        }
    }
    return islands
}

fun main() {
    val grid = listOf(
        "11000",
        "10010",
        "00110",
        "00001"
    )
    println("islands: ${countIslands(grid)}")            // 3
    println("all water: ${countIslands(listOf("000", "000"))}")
    println("one big island: ${countIslands(listOf("111", "111"))}")
}

Cost. Every cell is pushed at most once and has four neighbours to check, so a grid with R rows and C columns costs O(R × C) time and space. Swap the stack for a queue and you get BFS on the grid, which finds the shortest route through a maze.

6. Topological sort: ordering tasks with prerequisites

Say you must finish some courses before others. Calculus needs Algebra, Algebra needs Basic Math, and so on. In which order can you take everything? That order is a topological sort: a line-up of the vertices of a directed graph so that every arrow points forward.

It exists only for a DAG. If course A needs B and B needs A, no valid order exists. That is a cycle, and finding the sort is also how we detect it.

Kahn's algorithm

It uses the in-degree of each vertex: how many arrows point into it, that is, how many prerequisites are still unmet.

1. Count the in-degree of every vertex.
2. Put every vertex with in-degree 0 into a queue. They have no prerequisites, so they can go first.
3. Take one out and add it to the answer. For each vertex it points to, lower that vertex's in-degree by one (one prerequisite is now done). If it reaches 0, add it to the queue.
4. When the queue is empty: if the answer holds all V vertices, you have an order. If it holds fewer, the leftover vertices sit on a cycle.

// prereqs: pair (course, mustTakeFirst). Returns an order, or an empty list on a cycle.
fun courseOrder(n: Int, prereqs: List<Pair<Int, Int>>): List<Int> {
    val next = Array(n) { mutableListOf<Int>() }   // arrow: prerequisite -> course
    val inDegree = IntArray(n)
    for ((course, first) in prereqs) {
        next[first].add(course)
        inDegree[course]++
    }
    val queue = ArrayDeque<Int>()
    for (v in 0 until n) if (inDegree[v] == 0) queue.addLast(v)

    val order = ArrayList<Int>()
    while (queue.isNotEmpty()) {
        val u = queue.removeFirst()
        order.add(u)
        for (v in next[u]) {
            inDegree[v]--
            if (inDegree[v] == 0) queue.addLast(v)
        }
    }
    return if (order.size == n) order else emptyList()
}

fun main() {
    val names = listOf("Math", "Algebra", "Logic", "Calculus")
    val ok = courseOrder(4, listOf(1 to 0, 2 to 0, 3 to 1, 3 to 2))
    println("order: ${ok.map { names[it] }}")

    val cyclic = courseOrder(3, listOf(0 to 1, 1 to 2, 2 to 0))
    println("cyclic prerequisites: $cyclic   (empty means impossible)")

    println("no prerequisites: ${courseOrder(3, emptyList())}")
}

Cost. Every vertex enters the queue once and every edge lowers one in-degree once: O(V + E) time, O(V + E) space for the lists.

7. Dijkstra: shortest paths with weights

BFS counts edges, so it breaks down once edges have different costs. A road of 1 km and a road of 100 km are both “one edge”. For weighted graphs we use Dijkstra's algorithm (said “DYKE-struh”).

The idea is BFS with a smarter queue. Keep for every vertex the best distance found so far, starting at infinity except the start (0). Then repeat: take the unfinished vertex with the smallest known distance, and use its edges to see if any neighbour can be reached more cheaply. That check is called relaxing an edge:

if (dist[u] + weight < dist[v]) {
    dist[v] = dist[u] + weight    // found a cheaper way to v, through u
}

To find “the smallest known distance” quickly we use a priority queue (a heap, Part 4). It hands back the smallest item in O(log n).

Why the weights must not be negative

When Dijkstra takes the vertex with the smallest distance, it declares that distance final. That is safe only because any other route would have to go through vertices that are already at least as far away, and adding more non-negative edges can never make it shorter. A negative edge breaks this promise: a longer route could later become cheaper. For graphs with negative weights you need a different tool (see Bellman-Ford below).

import java.util.PriorityQueue

const val INF = Int.MAX_VALUE

// adj[u] holds pairs (neighbour, weight)
fun dijkstra(adj: Array<MutableList<Pair<Int, Int>>>, start: Int): Pair<IntArray, IntArray> {
    val dist = IntArray(adj.size) { INF }
    val parent = IntArray(adj.size) { -1 }
    dist[start] = 0
    // each entry is (distance when queued, vertex); smallest distance comes out first
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    pq.add(0 to start)

    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()
        if (d > dist[u]) continue            // stale entry: we already found better
        for ((v, w) in adj[u]) {
            if (d + w < dist[v]) {           // relax the edge
                dist[v] = d + w
                parent[v] = u
                pq.add(dist[v] to v)
            }
        }
    }
    return dist to parent
}

fun main() {
    val names = "ABCD"
    val adj = Array(4) { mutableListOf<Pair<Int, Int>>() }
    fun edge(a: Int, b: Int, w: Int) { adj[a].add(b to w); adj[b].add(a to w) }
    edge(0, 1, 4)   // A-B
    edge(0, 2, 1)   // A-C
    edge(2, 1, 2)   // C-B
    edge(1, 3, 1)   // B-D
    edge(2, 3, 5)   // C-D

    val (dist, parent) = dijkstra(adj, 0)
    for (v in 0 until 4) println("A to ${names[v]}: ${dist[v]}")

    val route = ArrayList<Char>()
    var cur = 3
    while (cur != -1) { route.add(names[cur]); cur = parent[cur] }
    println("route to D: ${route.reversed()}")
}

Cost. Each edge can add one entry to the heap, and each heap operation is O(log n). Total: O((V + E) log V) time and O(V + E) space. Unreachable vertices keep the value INF.

8. Union-find: tracking groups that merge

Sometimes you do not need paths at all. You only need to answer, again and again: “are these two things in the same group?” and “merge these two groups”. Think of friend circles forming as people become friends. A structure built for exactly this is the union-find, also called a disjoint set.

Every group is a little tree. Each element stores its parent in an array; the root of the tree is the group's leader, and the root is its own parent. Two operations:

• find(x): climb parents until you reach the root. Two elements are in the same group exactly when their roots match.
• union(a, b): find both roots and hang one root under the other.

Two small tricks keep the trees flat, which keeps everything fast:

• Path compression. While climbing in find, point every vertex on the way straight at the root. The next find is then almost free.
• Union by rank. Attach the shorter tree under the taller one, so trees never grow tall. (Rank is an upper estimate of the tree's height.)

class UnionFind(n: Int) {
    private val parent = IntArray(n) { it }   // everyone is their own leader
    private val rank = IntArray(n)
    var groups = n
        private set

    fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])   // path compression
        return parent[x]
    }

    // Returns false if a and b were already in the same group.
    fun union(a: Int, b: Int): Boolean {
        val ra = find(a)
        val rb = find(b)
        if (ra == rb) return false
        when {
            rank[ra] < rank[rb] -> parent[ra] = rb
            rank[ra] > rank[rb] -> parent[rb] = ra
            else -> {
                parent[rb] = ra
                rank[ra]++
            }
        }
        groups--
        return true
    }
}

fun main() {
    // 1. Connected components of an edge list, without any DFS
    val uf = UnionFind(6)
    uf.union(0, 1)
    uf.union(1, 2)
    uf.union(3, 4)
    println("groups: ${uf.groups}")                       // {0,1,2} {3,4} {5} -> 3
    println("0 and 2 together? ${uf.find(0) == uf.find(2)}")
    println("0 and 4 together? ${uf.find(0) == uf.find(4)}")
    println("redundant edge 0-2 merged anything? ${uf.union(0, 2)}")   // false: it would close a cycle

    // 2. Kruskal's idea: build a cheapest network that connects everything.
    //    Take edges from cheapest to dearest; keep an edge only if it joins two different groups.
    val roads = listOf(            // (weight, a, b)
        Triple(4, 0, 1), Triple(1, 0, 2), Triple(2, 2, 1), Triple(1, 1, 3), Triple(5, 2, 3)
    )
    val network = UnionFind(4)
    var total = 0
    for ((w, a, b) in roads.sortedBy { it.first }) {
        if (network.union(a, b)) {
            total += w
            println("keep edge $a-$b (cost $w)")
        }
    }
    println("cheapest way to connect all 4 towns costs $total")
}

Cost. With both tricks, each find and union takes nearly constant time. Formally it is O(α(n)), where α grows so slowly that it never exceeds 4 for any input that fits in a computer. Treat it as “practically O(1)”. Setup is O(n).

9. Other graph tools, and a complexity table

There are a few more famous graph algorithms. You do not need their code yet, but you should know which question each answers.

• Bellman-Ford. Shortest paths like Dijkstra, but it allows negative edge weights and can detect a negative cycle (a loop whose total cost is below zero, which makes “shortest” meaningless). It simply relaxes every edge V - 1 times, so it runs in O(V × E): slower, but more general.
• A* (A-star). Dijkstra with a hint. It adds a guess of the remaining distance to the goal (for a map, the straight-line distance) so it explores less. Used in games and route finding when you have one target, not all of them.
• Minimum spanning tree (MST). Given a connected weighted graph, pick the cheapest set of edges that still connects every vertex, with no cycles. Think of laying cable to link buildings at the least cost. Kruskal's algorithm (shown above) and Prim's algorithm both solve it.
• All-pairs shortest paths (Floyd-Warshall). Shortest distance between every pair of vertices, in O(V³), for small graphs.

Choosing the right tool

10. Practice

Five exercises, one for each big idea: walking, counting pieces, grids, ordering and weighted paths. Remember the edge cases: a single vertex, a graph in separate pieces, a cycle, and a target you cannot reach.

fun hasPath(n: Int, edges: List<Pair<Int, Int>>, from: Int, to: Int): Boolean {
    TODO("build the adjacency list, then walk from 'from' and look for 'to'")
}

fun hasPath(n: Int, edges: List<Pair<Int, Int>>, from: Int, to: Int): Boolean {
    val adj = Array(n) { mutableListOf<Int>() }
    for ((a, b) in edges) { adj[a].add(b); adj[b].add(a) }
    val seen = BooleanArray(n)
    val queue = ArrayDeque<Int>()
    seen[from] = true
    queue.addLast(from)
    while (queue.isNotEmpty()) {
        val u = queue.removeFirst()
        if (u == to) return true
        for (v in adj[u]) {
            if (!seen[v]) { seen[v] = true; queue.addLast(v) }
        }
    }
    return false
}

fun countComponents(n: Int, edges: List<Pair<Int, Int>>): Int {
    TODO("count the separate pieces")
}

fun countComponents(n: Int, edges: List<Pair<Int, Int>>): Int {
    val parent = IntArray(n) { it }
    fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])
        return parent[x]
    }
    var groups = n
    for ((a, b) in edges) {
        val ra = find(a)
        val rb = find(b)
        if (ra != rb) { parent[ra] = rb; groups-- }
    }
    return groups
}

fun countIslands(grid: List<String>): Int {
    TODO("flood fill from every unseen land cell")
}

fun countIslands(grid: List<String>): Int {
    if (grid.isEmpty()) return 0
    val rows = grid.size
    val cols = grid[0].length
    val seen = Array(rows) { BooleanArray(cols) }
    val dr = intArrayOf(-1, 1, 0, 0)
    val dc = intArrayOf(0, 0, -1, 1)
    var islands = 0
    for (r in 0 until rows) for (c in 0 until cols) {
        if (grid[r][c] != '1' || seen[r][c]) continue
        islands++
        val stack = ArrayDeque<Pair<Int, Int>>()
        seen[r][c] = true
        stack.addLast(r to c)
        while (stack.isNotEmpty()) {
            val (cr, cc) = stack.removeLast()
            for (d in 0 until 4) {
                val nr = cr + dr[d]
                val nc = cc + dc[d]
                if (nr in 0 until rows && nc in 0 until cols && grid[nr][nc] == '1' && !seen[nr][nc]) {
                    seen[nr][nc] = true
                    stack.addLast(nr to nc)
                }
            }
        }
    }
    return islands
}

fun canFinish(n: Int, prereqs: List<Pair<Int, Int>>): Boolean {
    TODO("Kahn's algorithm: can every vertex be taken off the queue?")
}

fun canFinish(n: Int, prereqs: List<Pair<Int, Int>>): Boolean {
    val next = Array(n) { mutableListOf<Int>() }
    val inDegree = IntArray(n)
    for ((course, first) in prereqs) {
        next[first].add(course)
        inDegree[course]++
    }
    val queue = ArrayDeque<Int>()
    for (v in 0 until n) if (inDegree[v] == 0) queue.addLast(v)
    var taken = 0
    while (queue.isNotEmpty()) {
        val u = queue.removeFirst()
        taken++
        for (v in next[u]) {
            inDegree[v]--
            if (inDegree[v] == 0) queue.addLast(v)
        }
    }
    return taken == n
}

fun shortestDistances(n: Int, edges: List<Triple<Int, Int, Int>>, src: Int): List<Int> {
    TODO("Dijkstra with a PriorityQueue")
}

fun shortestDistances(n: Int, edges: List<Triple<Int, Int, Int>>, src: Int): List<Int> {
    val adj = Array(n) { mutableListOf<Pair<Int, Int>>() }
    for ((a, b, w) in edges) adj[a].add(b to w)
    val dist = IntArray(n) { Int.MAX_VALUE }
    dist[src] = 0
    val pq = java.util.PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    pq.add(0 to src)
    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()
        if (d > dist[u]) continue
        for ((v, w) in adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w
                pq.add(dist[v] to v)
            }
        }
    }
    return dist.map { if (it == Int.MAX_VALUE) -1 else it }
}

11. Takeaways

• Ask first: what are the vertices, and what are the edges?
• Mark vertices as visited, or a cycle will trap your walk forever.
• BFS for fewest steps, DFS for exploring, Kahn for ordering, Dijkstra for weighted shortest paths, union-find for merging groups.
• Most graph algorithms cost O(V + E); adding a heap adds a log V factor.
• Test the awkward cases: one vertex, a disconnected graph, a cycle, an unreachable target.
• Next up: sorting and searching, the other great family of everyday algorithms.