BFS, DFS, Topological Sort & Shortest Path

The last lesson stored a graph and warned that walking one is hard — cycles can trap you in endless loops. The discipline that tames them is a single visited set, and on top of it sit four ideas that answer almost everything GATE asks: BFS and DFS (the two traversals), topological sort (ordering a DAG), and shortest path (BFS when unweighted, Dijkstra when weighted). These are not just exam fodder — topological sort is exactly how Spark and Airflow decide the run order of a task DAG, and shortest-path search is the core of routing, recommendation, and graph-analytics work.

BFS and DFS — the two traversals

• BFS (Breadth-First Search) uses a queue (FIFO). Enqueue the source, then repeatedly dequeue a vertex and enqueue its unvisited neighbours. It fans out in rings: every vertex at distance d is reached before any at distance d + 1. That is exactly why BFS gives the shortest path in an unweighted graph — the first time you reach a vertex, you reached it in the fewest edges.
• DFS (Depth-First Search) uses a stack (or recursion). It commits to one branch, plunging as deep as possible before backtracking to the last fork. DFS is the engine behind cycle detection and topological sort.

Both visit every reachable vertex exactly once (a visited set prevents loops); they differ only in the order — queue for breadth, stack for depth, the two structures from earlier in this chapter doing the steering. Step through both side by side here:

Topological sort — only for a DAG

A topological sort of a directed acyclic graph is a linear ordering of its vertices such that every edge u → v points forward (u appears before v). It is the natural answer to “in what order can I run these tasks so each prerequisite comes first?”

Two facts GATE leans on:

• A topological order exists if and only if the graph is a DAG. A directed cycle makes it impossible — the vertices on the cycle would each have to come before the other.
• It is usually not unique. Whenever two vertices have no path forcing an order between them, either can come first, and each independent choice multiplies the count of valid orderings.

Shortest path — BFS vs Dijkstra

When edges are unweighted, BFS already solves shortest paths — its layer numbers are the minimum edge counts. Add weights (a toll road costs more than a side street) and BFS breaks, because four cheap edges can beat one expensive edge, but BFS counts only hops.

Dijkstra’s algorithm fixes this with one greedy rule: always expand the cheapest-so-far unvisited vertex next, and relax its neighbours (if going through this vertex beats a neighbour’s recorded distance, lower it). It is correct only when all edge weights are non-negative. Step through a relaxation cascade here:

How GATE asks this

Expect a NAT for “the BFS distance from S to vertex X” or “the number of valid topological orderings of this DAG”, and an MCQ/MSQ on properties — which of several sequences are valid topological orderings (the 2024 paper’s Q.51 was exactly this MSQ; its DAG admits 12 orderings in all), when a topological sort exists, BFS vs DFS data structures, or when you must switch from BFS to Dijkstra. Read carefully for the word weighted: it decides BFS vs Dijkstra.

Worked example

Topological order of a DAG. Take edges A → B, A → C, B → D, C → D. Vertex A has no incoming edge, so it goes first; D has every other vertex before it, so it goes last. B and C are independent of each other, so either can come second. Two valid orders:

A, B, C, D        and        A, C, B, D

So this DAG has 2 valid topological orderings — a direct illustration that the order exists (it is a DAG) but is not unique.

BFS distances on the 5-vertex graph above. Run BFS from S on the undirected, unweighted graph drawn earlier (edges S-A, S-B, A-B, A-C, B-D):

queue: [S]                 visit S, dist[S] = 0
dequeue S → enqueue A, B   dist[A] = 1, dist[B] = 1
dequeue A → enqueue C      dist[C] = 2   (B already seen)
dequeue B → enqueue D      dist[D] = 2

So dist = {S:0, A:1, B:1, C:2, D:2}. The farthest vertices are C and D at distance 2 — the minimum number of edges to reach each from S, exactly because BFS visits in rings.

A question to carry forward

That closes the data-structures-and-algorithms chapter. Look back at everything in it — the array, the linked list, the hash table, the tree, the graph. Every one lives in a single program’s memory, and every one evaporates the instant that program exits. That is fine for a computation that runs and finishes. But the data a real organisation depends on cannot be so fragile: a bank’s accounts, a hospital’s records, a retailer’s orders must outlive any program — persisting on disk, surviving crashes, and answering questions from hundreds of users at the same moment without ever corrupting a record. Here is the thread into the next chapter: what disciplined way of organising data makes that durability and concurrency possible — and what beautifully simple idea, just rows and columns with a precise algebra behind it, became the foundation of nearly every database in the world?

In one breath

• BFS = queue (FIFO), fans out in rings → shortest path on an UNWEIGHTED graph (first arrival = fewest edges). DFS = stack/recursion, plunges deep → cycle detection, topo sort.
• A visited set stops both from looping forever on cycles.
• Topological sort: linear order with every edge pointing forward; exists iff DAG, usually not unique (GATE 2024 Q.51 DAG had 12 orderings; no edges on n vertices → n!).
• Shortest path: BFS if unweighted; Dijkstra (greedy: expand cheapest, relax neighbours) if weighted — correct only for non-negative weights.
• Read for the word weighted — it is what flips the answer from BFS to Dijkstra.

Practice