Week 12: Graphs: Traversal, Shortest Paths & Union-Find

1. Graph Representations

A graph is a set of vertices connected by edges, and how you store those edges shapes every algorithm you'll write this week. The two standard choices are the adjacency list (a list of neighbors per vertex) and the adjacency matrix (an n × n grid of 0s and 1s).

representations.cpp

#include <vector>
using namespace std;

int n = 5;   // vertices labeled 0..n-1

// Adjacency LIST -- O(V + E) space, efficient for sparse graphs
vector<vector<int>> adjList(n);
void addEdgeList(int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u);   // omit this line for a DIRECTED graph
}

// Weighted adjacency list: pair<neighbor, weight>
vector<vector<pair<int,int>>> weightedAdjList(n);
void addWeightedEdge(int u, int v, int w) {
    weightedAdjList[u].push_back({v, w});
    weightedAdjList[v].push_back({u, w});
}

// Adjacency MATRIX -- O(V^2) space, O(1) edge lookup
vector<vector<int>> adjMatrix(n, vector<int>(n, 0));
void addEdgeMatrix(int u, int v) {
    adjMatrix[u][v] = 1;
    adjMatrix[v][u] = 1;
}

Most interview and real-world graphs are sparse (E is much closer to V than to V²), which makes the adjacency list the default choice — it uses only as much memory as there are edges, versus a fixed V² for the matrix regardless of how few edges actually exist.

Let the constraints choose for you

If a problem states V up to 10⁵, an adjacency matrix would need on the order of 10¹⁰ cells — an instant memory-limit failure. Constraints like that are a direct signal to reach for an adjacency list before writing a single line of traversal code.

2. BFS & Connected Components

Breadth-first search explores a graph level by level using a queue — exactly the same shape as the level-order tree traversal from Week 9, generalized to allow revisiting-prevention via a visited or dist array since graphs can contain cycles that trees can't.

bfs.cpp

#include <vector>
#include <queue>
using namespace std;

// Shortest distance (in edges) from start to every reachable vertex -- O(V + E)
vector<int> bfs(int start, const vector<vector<int>>& adj) {
    vector<int> dist(adj.size(), -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// Number of connected components in an undirected graph -- O(V + E)
int countComponents(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    int components = 0;

    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        components++;
        queue<int> q;
        q.push(i);
        visited[i] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return components;
}

BFS = shortest path, but only in unweighted graphs

Because BFS explores level by level, the first time it reaches a vertex is guaranteed to be via the fewest possible edges. That guarantee disappears the moment edges have different weights — that's precisely the gap Dijkstra's algorithm fills later in this lesson.

3. DFS & Topological Sort

Depth-first search dives as deep as possible before backtracking, using recursion (or an explicit stack) instead of a queue. Run on a directed acyclic graph (DAG), a postorder DFS produces a topological order — a linear ordering where every edge points from an earlier vertex to a later one, useful for scheduling tasks with dependencies.

dfs_topo.cpp

#include <vector>
#include <algorithm>
using namespace std;

// Standard recursive DFS -- O(V + E)
void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) dfs(v, adj, visited);
    }
}

void topoDfs(int u, const vector<vector<int>>& adj, vector<bool>& visited, vector<int>& order) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) topoDfs(v, adj, visited, order);
    }
    order.push_back(u);   // push AFTER visiting every descendant
}

// Topological sort of a DAG -- O(V + E)
vector<int> topologicalSort(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<bool> visited(n, false);
    vector<int> order;

    for (int i = 0; i < n; i++) {
        if (!visited[i]) topoDfs(i, adj, visited, order);
    }
    reverse(order.begin(), order.end());   // postorder reversed = valid topo order
    return order;
}

A vertex is only appended to order after every vertex reachable from it has already been appended — so by the time you reverse the list, every dependency comes before the thing that depends on it. An alternative, Kahn's algorithm, builds the same ordering iteratively with a queue of zero-indegree vertices instead of recursion.

Foreshadowing Week 13

Once you have a topological order, you can compute a DP recurrence over a DAG in a single pass — process vertices in topo order and every dependency's answer is guaranteed to already be computed. That's exactly the structure behind DP-on-DAG problems you'll meet starting next week.

4. Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source to every other vertex in a weighted graph with non-negative edge weights. It's a greedy algorithm — the vertex popped off a min-heap with the smallest known distance is guaranteed to already have its final, shortest distance:

dijkstra.cpp

#include <vector>
#include <queue>
#include <climits>
using namespace std;

// Shortest distance from start to every vertex -- O((V + E) log V)
vector<int> dijkstra(int start, const vector<vector<pair<int,int>>>& adj) {
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;

    // min-heap of {distance, vertex}
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;   // stale entry -- a shorter path to u was already found

        for (auto& [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

std::priority_queue has no built-in "decrease key" operation, so instead of updating an existing entry, the algorithm just pushes a new, smaller entry and leaves the old one in place — the stale-entry check (if (d > dist[u]) continue;) skips it cheaply when it's eventually popped.

Why non-negative weights are non-negotiable

Dijkstra's greedy step assumes that once a vertex is popped with the smallest current distance, no later path could possibly beat it — but a negative edge could reduce a path's total cost after the fact, breaking that assumption. Graphs with negative edges need Bellman-Ford instead, which handles them in O(V × E) at the cost of being slower.

5. Union-Find with Path Compression

Union-Find (disjoint set union) answers one question extremely fast, repeatedly: "are these two elements in the same connected group?" Each element starts in its own set; unite merges two sets, and find returns a representative for an element's current set.

union_find.cpp

#include <vector>
#include <numeric>
using namespace std;

class UnionFind {
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);   // parent[i] = i
    }

    // Path compression: flatten the tree on every find() call
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    // Union by rank: attach the shorter tree under the taller one
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;   // already connected

        if (rank[rx] < rank[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
        return true;
    }

private:
    vector<int> parent;
    vector<int> rank;
};

With both path compression and union by rank, a sequence of m operations on n elements runs in O(m α(n)) total, where α is the inverse Ackermann function — for any input size that could ever exist in practice, that's effectively constant time per operation.

Watch for these interview signals

"Number of provinces," "redundant connection," and "accounts merge" style problems are all Union-Find in disguise — the tell is a question about grouping or connectivity that would otherwise require re-running BFS/DFS from scratch after every new edge. Union-Find is also the backbone of Kruskal's minimum-spanning-tree algorithm.

6. Hands-on Exercise

Hands-on

Build a Network Latency & Course Scheduler Checker

Apply BFS, DFS, Dijkstra, and Union-Find to two classic graph problems back to back.

Requirements:

Represent a weighted, directed graph of network nodes using a weighted adjacency list.
Implement dijkstra to compute the time for a signal to reach every node from a source, and return -1 for any node that stays unreachable.
Implement UnionFind and use it to detect whether adding a given edge to an undirected graph would create a cycle.
Implement topologicalSort and use it to check whether a list of course prerequisites (directed edges) can all be completed — return an empty vector if a cycle makes it impossible.
Test with a graph containing an unreachable node and a graph containing a cycle, confirming both failure cases are reported correctly.
State the time complexity of each of the four functions you wrote in a comment above it.

Hint

For the course scheduler, a cycle exists exactly when topologicalSort's result has fewer than n vertices — any vertex stuck in a cycle never gets its indegree/visited state resolved, so it's silently left out of the order.

7. Knowledge Check

Four quick questions. Expand each to check your answer.

When would you choose an adjacency matrix over an adjacency list, despite its worse memory usage?

A matrix is worth its O(V²) memory cost when V is small and you need O(1) "is there an edge between u and v?" lookups very frequently, or when the graph is dense enough that E is already close to V² anyway. For large or sparse graphs the memory cost dominates and an adjacency list wins on every metric that matters.

Why does the `if (d > dist[u]) continue;` line in Dijkstra matter, given that `std::priority_queue` can't update an existing entry's key?

Because the heap can't decrease an existing key, the algorithm pushes a fresh, smaller entry whenever a shorter path to a vertex is found, leaving the older, larger entry sitting in the heap. That stale entry will eventually be popped, and the check discards it in O(1) instead of letting it incorrectly relax edges using an outdated, larger distance.

Why does topological sort only work on a DAG, and how would you detect that a graph has a cycle before attempting it?

A topological order requires every edge to point from earlier to later in the sequence, but a cycle means some vertex would have to appear both before and after another vertex in its own cycle — a contradiction that makes no valid ordering exist. You can detect a cycle by running the DFS-based or Kahn's-algorithm-based topo sort and checking whether the resulting order contains fewer vertices than the graph actually has.

Why does path compression alone make Union-Find's `find()` nearly constant time, and what does adding union by rank get you on top of that?

Path compression rewires every visited node directly to the set's root during a find() call, so future lookups on those same nodes become O(1) instead of retraversing a long chain. Union by rank prevents those chains from ever growing tall in the first place, by always attaching the shorter tree under the taller one — together the two techniques bring the amortized cost down to O(α(n)), effectively constant.