Learn DSA Part 11: Graphs - BFS, DFS, Topological Sort, Dijkstra and Union-Find

Graphs model anything made of connected things: road maps, social networks, course prerequisites, web pages, even a grid of land and water. Graph questions feel hard at first, but nearly all of them reduce to a small toolkit: BFS, DFS, topological sort, Dijkstra's algorithm and union-find. Learn these five and you can handle most graph problems in interviews.

This is Part 11 of the Learn DSA series. We cover how to represent graphs, traverse them, order tasks with dependencies, find shortest paths and track connected components. Code is in C++ and Java.

1. Representing a graph

A graph has vertices (nodes) and edges connecting them. Edges can be directed (one-way, like prerequisites) or undirected (two-way, like friendships), and weighted (distances, costs) or unweighted. V is the number of vertices and E the number of edges.

In code, an adjacency list is vector<vector<int>> in C++ or List<List<Integer>> in Java, built from an edge list. A 2D grid is an implicit graph: each cell is a vertex connected to its up, down, left and right neighbours.

2. BFS and DFS

Breadth-first search explores the graph in layers using a queue. In an unweighted graph, the first time BFS reaches a vertex is along a shortest path, so BFS is the tool for "minimum number of steps" questions.

// BFS: shortest number of edges from src to every vertex (-1 = unreachable)
vector<int> bfs(const vector<vector<int>>& adj, int src) {
    vector<int> dist(adj.size(), -1);
    queue<int> q;
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {            // not visited yet
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;
}

// BFS: shortest number of edges from src to every vertex (-1 = unreachable)
static int[] bfs(List<List<Integer>> adj, int src) {
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, -1);
    Deque<Integer> q = new ArrayDeque<>();
    dist[src] = 0;
    q.offer(src);
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {            // not visited yet
                dist[v] = dist[u] + 1;
                q.offer(v);
            }
        }
    }
    return dist;
}

Depth-first search goes as deep as possible before backtracking, using recursion or an explicit stack. It is natural for counting connected components (Number of Islands), detecting cycles, flood fill, and exploring all paths. Both BFS and DFS run in O(V + E) time.

• Always keep a visited set or array, or you will loop forever on cycles. Mark a node visited when you push it into the queue, not when you pop it, to avoid adding it twice.
• Multi-source BFS: push all starting points first (for example every rotten orange) to compute distances from the nearest source in one pass.
• Bipartite check: colour nodes with two colours by BFS or DFS; a conflict means the graph is not bipartite.

3. Topological sort for dependencies

In a directed acyclic graph (DAG), a topological order lists vertices so that every edge goes from earlier to later: an order in which to take courses or build modules. Kahn's algorithm repeatedly takes vertices with no remaining incoming edges (in-degree 0).

// Kahn's algorithm: topological order, or empty if there is a cycle
vector<int> topoSort(int n, const vector<vector<int>>& adj) {
    vector<int> indeg(n, 0), order;
    for (int u = 0; u < n; u++) for (int v : adj[u]) indeg[v]++;
    queue<int> q;
    for (int u = 0; u < n; u++) if (indeg[u] == 0) q.push(u);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    if ((int)order.size() < n) return {};   // cycle detected
    return order;
}

// Kahn's algorithm: topological order, or empty if there is a cycle
static List<Integer> topoSort(int n, List<List<Integer>> adj) {
    int[] indeg = new int[n];
    for (int u = 0; u < n; u++) for (int v : adj.get(u)) indeg[v]++;
    Deque<Integer> q = new ArrayDeque<>();
    for (int u = 0; u < n; u++) if (indeg[u] == 0) q.offer(u);
    List<Integer> order = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
    }
    return order.size() < n ? new ArrayList<>() : order;  // empty = cycle
}

If the result contains fewer than V vertices, some vertices never reached in-degree 0, which means the graph has a cycle. That is exactly how Course Schedule is solved. A DFS-based version (add a vertex to the order after visiting all its descendants, then reverse) also works and detects cycles by tracking vertices on the current recursion path.

4. Shortest paths: Dijkstra and friends

For weighted graphs with non-negative weights, Dijkstra's algorithm keeps a min-heap (Part 10) of tentative distances and always settles the closest unsettled vertex. With a binary heap it runs in O((V + E) log V).

// Dijkstra: adj[u] = list of {v, weight}, weights >= 0
vector<long long> dijkstra(const vector<vector<pair<int,int>>>& adj, int src) {
    const long long INF = LLONG_MAX;
    vector<long long> dist(adj.size(), INF);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>,
                   greater<pair<long long,int>>> pq;   // {dist, vertex}
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                   // stale entry
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

// Dijkstra: adj.get(u) = list of {v, weight}, weights >= 0
static long[] dijkstra(List<List<int[]>> adj, int src) {
    long[] dist = new long[adj.size()];
    Arrays.fill(dist, Long.MAX_VALUE);
    PriorityQueue<long[]> pq =
        new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));  // {dist, vertex}
    dist[src] = 0;
    pq.offer(new long[]{0, src});
    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        int u = (int) top[1];
        if (top[0] > dist[u]) continue;              // stale entry
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new long[]{dist[v], v});
            }
        }
    }
    return dist;
}

Dijkstra fails with negative weights because a settled vertex might later be reachable more cheaply. Cheapest Flights Within K Stops is the classic Bellman-Ford style problem.

5. Union-find for connectivity

A disjoint set union (union-find) keeps track of which vertices are in the same component as edges are added. It supports two operations: find(x) returns the representative of x's group, and union(a, b) merges two groups.

• Path compression: during find, point every visited node directly at the root.
• Union by rank or size: attach the smaller tree under the larger one.

With both optimisations, each operation is effectively O(1) (the inverse Ackermann function). Union-find counts connected components, detects a cycle in an undirected graph (an edge whose endpoints are already connected), solves Redundant Connection and Accounts Merge, and powers Kruskal's minimum spanning tree: sort edges by weight and add each one that joins two different components. Prim's algorithm builds the same tree with a min-heap instead.

Practice problems

These are classic LeetCode-style problems, listed from easy to hard. For each one, define the vertices and edges first, then choose BFS, DFS, topological sort, Dijkstra or union-find.

1. Flood Fill (easy)
2. Find if Path Exists in Graph (easy)
3. Number of Islands (medium)
4. Clone Graph (medium)
5. Rotting Oranges (medium, multi-source BFS)
6. Course Schedule (medium, topological sort)
7. Course Schedule II (medium)
8. Pacific Atlantic Water Flow (medium)
9. Is Graph Bipartite? (medium)
10. Redundant Connection (medium, union-find)
11. Network Delay Time (medium, Dijkstra)
12. Cheapest Flights Within K Stops (medium)
13. Word Ladder (hard, BFS)
14. Alien Dictionary (hard, topological sort)