Elementary Graph Algorithms: BFS, DFS, Topological Sort and Strongly Connected Components

By the end of this lesson you will be able to represent a graph two different ways, trace BFS and DFS by hand (colours, queues, discovery/finish timestamps), classify every edge a DFS meets as tree/back/forward/cross, compute a topological sort of a DAG, and find every strongly connected component of a directed graph with Kosaraju's two-pass DFS — the same machinery behind course-prerequisite checkers, dependency resolvers, "number of islands" puzzles, and dead-code/cycle detectors.

1. Representing a graph: adjacency list vs. adjacency matrix

Think of a graph as a map of friendships or roads: vertices (dots) are people/cities, edges (lines) are the friendships/roads between them. An edge can be directed (a one-way road, drawn with an arrow: "Alice follows Bob" doesn't mean Bob follows Alice) or undirected (a two-way road: "Alice and Bob are friends" is symmetric). We write a graph as G = (V, E) — a set of vertices V and a set of edges E connecting them.

There are exactly two standard ways to store a graph in memory, and this lesson's algorithms use adjacency lists throughout:

Representation	What it stores	Space	Best for
Adjacency list `adj[u]`	For every vertex `u`, the list of vertices `u` points to (its neighbours).	`Θ(V + E)`	Sparse graphs (few edges) — almost every real-world graph. Visiting all of a vertex's neighbours is fast; checking "does edge (u,v) exist?" requires scanning `adj[u]`.
Adjacency matrix `a[i][j]`	A `V × V` grid; `a[i][j] = 1` if edge `(i,j)` exists, else 0.	`Θ(V²)`	Dense graphs, or when you need an `O(1)` "does this edge exist?" check. An undirected graph's matrix is always symmetric (`a = a^T`).

Weighted graphs store the weight w(u,v) alongside each neighbour in adj[u], or as the matrix entry instead of a bare 1. This lesson's graphs are unweighted, so we only track "edge exists or not".

The same two structures in Dart

In Dart a vertex is just a list index, so the page example a, b, c, d becomes 0, 1, 2, 3: vertex k is the list index k, adj[u] is its list of neighbours, and a[u][v] is the matrix cell for the edge (u, v).

The space claims Θ(V+E) vs Θ(V²) as code: the lengths of all adjacency lists add up to E (directed) or 2E (undirected, each edge is stored in both lists), while the matrix always has V·V cells.

The transpose G^T (every edge reversed) reads each edge (u,v) once and stores (v,u): Θ(V+E) time.

Input size → what is feasible: V ≤ 10³ → a matrix (10⁶ cells) is fine; V = 10⁵ → a matrix needs 10¹⁰ cells (about 10 GB at one byte each) — use adjacency lists (V + 2E entries). The examples above have V = 4, E = 4.

A very common beginner assumption: "adjacency list" and "adjacency matrix" are interchangeable. They are NOT the same asymptotically. On a graph with V = 10,000 vertices and only E = 20,000 edges (sparse, like a typical social network or road map), the adjacency list uses about 30,000 total entries (50,000 if every undirected edge is stored in both of its endpoints’ lists), while the adjacency matrix needs 100,000,000 cells — most of them wastefully storing 0. Always default to adjacency lists unless you specifically need O(1) edge lookups on a dense graph.

The transpose G^T is the same graph with every edge reversed. With an adjacency list this costs O(V+E) (build V empty lists, then for each edge (u,v) of G, add u to the new list of v). With an adjacency matrix it is literally the matrix transpose, O(V²). Section 6 uses G^T to find strongly connected components.

A graph is vertices + edges. Adjacency lists (Θ(V+E) space) are the default for sparse graphs and are what BFS, DFS, topological sort and SCC in this lesson all use; adjacency matrices (Θ(V²) space) trade memory for O(1) edge-existence checks and are better only for dense graphs.

2. Breadth-first search: bfs

Imagine dropping a pebble into a pond: ripples spread outward in perfect rings — everyone at distance 1 hears the splash before anyone at distance 2. BFS explores a graph the same way from a chosen source vertex s: it visits every vertex at distance 1 (one edge away) before visiting any vertex at distance 2, then all of distance 2 before distance 3, and so on. This "ripple" order is exactly what makes BFS the right tool whenever you need the fewest-edges path.

While it runs, BFS keeps a colour for every vertex: white = not yet discovered, gray = discovered but not yet fully explored (some of its neighbours may still be unchecked — gray vertices are exactly the ones currently sitting in the queue), black = discovered AND every neighbour has been checked (fully finished). Two more facts are stored per vertex: d[v] = the distance (number of edges) from s to v, and parent[v] = the vertex that first discovered v (used to reconstruct the shortest path — Section 3). A vertex is white exactly while d[v] = ∞.

Try your own graph. Enter an edge list. Use u-v for an undirected edge, u->v for a directed edge (a graph that contains any -> is treated as fully directed; if none appear, every - edge is treated as two-way). You may also list a lone vertex name to add an isolated vertex. In a directed graph a plain u-v just means u->v. Self-loops (a-a), repeated edges and disconnected graphs are all accepted (at most 12 vertices).

BFS in Dart

The comments in the code name the pseudocode lines (lines 1–3 initialise every vertex; here that is the two List.filled calls). d[v] == inf means “WHITE”. parent[v] == -1 is NIL. The queue is a list plus a head index: removeAt(0) would shift every element and make BFS quadratic, while q[head++] is O(1).

The running-time argument as a measurement: count the vertices dequeued and the edges examined.

Input size → what is feasible: V, E ≤ 10⁶ → BFS does about V + E = 2·10⁶ steps (< 0.1 s); an O(V·E) idea would need 10¹². The examples above have V ≤ 7, E ≤ 8.

Running time. Every vertex is enqueued and dequeued at most once — O(V) total queue work. Every vertex's adjacency list is scanned exactly once, when that vertex is dequeued; summed over all vertices, that is Θ(E) (each edge is examined once for a directed graph, twice for undirected). Initialization costs Θ(V). Total: O(V + E) — linear in the size of the adjacency-list representation.

Why BFS distances are exactly right. Write δ(s,v) for the true fewest-edges distance. Fact 1: d[v] ≥ δ(s,v) always (an estimate that comes from a real walk can never be shorter than the shortest walk) — by induction on the order vertices are enqueued. Fact 2: the queue is always "sorted to within 1": if it holds v₁,...,vₛ front to back, then d[v₁] ≤ ... ≤ d[vₛ] ≤ d[v₁] + 1, so all of distance k leaves the queue before any of distance k+1 does. Now suppose some vertex ended with a too-large distance and take the one with the smallest true distance. Its predecessor on a real shortest path has the right distance, was dequeued at some point, and at that moment would have discovered our vertex with the right distance (unless it had already been discovered, which by Fact 2 could only happen with a distance that is no larger) — a contradiction. So every d[v] ends up exactly δ(s,v).

BFS's shortest-path guarantee only holds for unweighted graphs (or graphs where every edge has equal weight). If edges have different weights, "fewest edges" and "least total weight" can disagree — you need Dijkstra's algorithm (shortest paths with weights) instead.

BFS explores ripple-by-ripple from a source using a FIFO queue of gray vertices. White = undiscovered, gray = discovered/in-queue, black = finished. Every vertex ends with d[v] = δ(s,v), the true shortest-path distance in edges, and parent[v] pointing back along a shortest path. Runs in O(V+E).

3. printPath: reconstructing the path BFS found

BFS leaves every discovered vertex holding a single breadcrumb: parent[v], "who found me". printPath follows breadcrumbs backward from the destination all the way to the source, then prints them forward — like unwinding a ball of string you dropped as you walked, then reading the trail from the start.

printPath recurses on parent[v] before printing v itself — that's what turns a backward breadcrumb-trail into a forward-printed path.

printPath in Dart

The pseudocode prints as it unwinds; Dart returns the list [s, ..., v] instead (same recursion, same order: recurse on parent[v] first, then add v). For paths longer than about 5000 vertices, collect v, parent[v], parent[parent[v]], ... in a loop and reverse it instead of recursing.

Input size → what is feasible: a path has at most V − 1 edges, so printPath costs O(path length) ≤ O(V); with V ≤ 5000 the recursion is safe (checked in the verification program), beyond that use the loop version.

If you print v BEFORE recursing (instead of after), you print the path backwards (destination to source) — the recursive call must come first so that everything "further back" on the path finishes printing before the current vertex's turn.

printPath(parent, s, v): base case v = s prints s; if v has no parent, no path exists; otherwise recurse on parent[v] FIRST, then print v — turning backward parent pointers into a forward-printed path in time linear in the path's length.

4. Depth-first search: dfs & dfsVisit

Imagine exploring a maze by always taking the FIRST unexplored corridor you see, going as deep as possible, and only backtracking when you hit a dead end (every corridor from here has already been explored). That is DFS — the opposite exploration strategy from BFS's "spread out evenly" ripples. DFS may (unlike BFS) start fresh explorations from multiple sources, building a whole forest of trees, not just one tree.

DFS timestamps every vertex twice: d[v] = the moment it is first discovered (turns gray), and f[v] = the moment its exploration finishes (turns black). These come from one global clock (time) that ticks once per event, so every timestamp from 1 to 2V is used exactly once, and always d[v] < f[v].

Reading the two code panels. DFS is written as two procedures: dfs (7 lines: set up, then start a tree from every still-white vertex) and dfsVisit(u) (10 lines: explore everything reachable from u). So every DFS animation shows dfs in the normal code panel and dfsVisit in a second panel under the graph, and each caption says which procedure its line numbers belong to. The dfs panel keeps line 7 (the call) lit while a tree is being explored, because the whole exploration happens inside that call.

Try your own graph. The default below is a directed graph written with arrows (u->v); it already contains one of every edge type so you can see tree/back/forward/cross all at once before you edit it. Try a-b, b-c, c-a (undirected, so no forward/cross), a-a (self-loop) or a lone name for an isolated vertex.

dfs and dfsVisit in Dart

The class below keeps the state in lists: color (0 WHITE, 1 GRAY, 2 BLACK), parent, d, f and the global time. The constructor does dfs lines 2–4, the method dfs is lines 5–7, and dfsVisit is lines 1–10 of its own panel. One extra line records the edge type using edgeType, the colour table of the next subsection.

Running time as a measurement: dfsVisit is called once per vertex and each adjacency list is scanned once.

Input size → what is feasible: V, E ≤ 10⁵ → Θ(V+E) ≈ 3·10⁵ steps; recursion depth can reach V and Dart overflows its stack somewhere between 10⁴ and 3·10⁴ frames, so keep V ≤ 5000 for the recursive version, or use an explicit stack for more. The examples above have V ≤ 6.

Edge classification

Every edge (u,v) that DFS examines (from u, currently gray, looking at neighbour v) gets classified by v's colour at that instant:

Colour of `v` when examined	Edge type	Meaning
white	Tree edge	`v` is discovered for the very first time through this edge; it becomes part of the DFS forest.
gray	Back edge	`v` is an ancestor of `u`, still open on the recursion stack — this edge points "backwards" up the tree (includes self-loops).
black, `d[u] < d[v]`	Forward edge	`v` is an already-finished descendant of `u` — a "shortcut" down the tree.
black, `d[u] > d[v]`	Cross edge	`v` is in an already-finished, unrelated part of the forest (a different subtree or an earlier tree entirely).

The undirected-graph rule: running DFS on an undirected graph produces only tree and back edges — never a forward or cross edge. Why: an undirected edge is one edge that sits in two adjacency lists, and it is classified once, the first time DFS meets it from either end. Say d[u] < d[v]. Then v is discovered while u is still open, so v finishes before u. If DFS meets the edge first from u, v is still white (tree edge); if it meets it first from v, u is still gray (back edge). The “black” cases never arise. That is why, in the undirected animations, the second time an edge is scanned (from its other end) the caption says it was already classified.

Edge classification in code: the colour of v at the moment the edge (u,v) is examined decides the type. The kind map in the class above stores it; for an undirected graph the edge is stored under one normalised key, so it is classified only the first time it is met.

The parenthesis theorem. Write each vertex's lifetime as a pair of parentheses: ( at d[v], ) at f[v]. For ANY two vertices u, v, their parenthesis pairs are either completely disjoint (f[u] < d[v] or f[v] < d[u] — neither is an ancestor of the other) or completely nested (one entirely inside the other — the inner one is a descendant of the outer one). They can never partially overlap, like ( [ ) ]. Equivalently (the nesting rule): v is a proper descendant of u if and only if d[u] < d[v] < f[v] < f[u] — you can read the whole ancestor/descendant structure straight off the d/f numbers, no tree pointers needed.

The parenthesis theorem and the nesting rule as code (checked on every pair of vertices of random graphs in the verification program):

The white-path theorem. In a DFS forest, v is a descendant of u if and only if, at the moment u is discovered (time d[u]), there is a path from u to v made entirely of white vertices. Picture u stepping into a dark maze where every room is unlit (white): DFS keeps walking and lights up (discovers) every room it can reach through a chain of unlit rooms before u is allowed to finish, but it can never light a room whose only routes pass through rooms that were already lit before u arrived. (⇐) If a white path exists, induction along it shows each vertex on it is discovered before u finishes, so its interval nests inside u’s (nesting rule). (⇒) If v is a descendant, every vertex on the tree path from u to v has a larger discovery time than u, so all of them were still white at time d[u]. This theorem is the workhorse behind the back-edge lemma (a cycle forces a back edge) and the finish-order lemma for components (SCC).

A path from u to v with d[u] < d[v] does NOT make v a descendant of u. The white-path theorem says the path must be white at time d[u]. Counterexample: edges r->s, r->v, s->t, t->r, DFS started at r (with s listed before v in adj[r]). Then d[r]=1, d[s]=2, d[t]=3; t sees the gray r (a back edge) and finishes at f[t]=4, then s finishes at 5; only then does r reach v, so d[v]=6, f[v]=7, f[r]=8. There is a path t→r→v and d[t] < d[v], yet the intervals [3,4] and [6,7] are disjoint: the path runs through r, which was already gray, not white. (Paste r->s, r->v, s->t, t->r into the DFS “your own graph” box to watch it.) A single edge is different: if (u,v) is examined and d[u] < d[v], then v was white (tree edge) or black-and-nested (forward edge), so it really is a descendant. The safe rule for reading structure off timestamps is always the FULL nesting condition, never discovery time alone.

The white-path theorem as code: a vertex w is still white at time d[u] exactly when d[w] > d[u], so “is there a white path?” is a plain search that only enters such vertices. It agrees with the real descendant relation on every pair; on the r, s, t, v graph above it says false for the pair (t, v).

Running time. dfsVisit is called exactly once per vertex (a vertex is only visited while white, and it's immediately coloured gray). Each call scans its own adjacency list once; summed over all vertices that is Θ(E). Total: Θ(V + E).

DFS goes as deep as possible before backtracking, timestamping discovery (d) and finish (f) from one global clock. White/gray/black have the same meaning as BFS, but DFS additionally classifies every edge as tree/back/forward/cross by the colour of the far endpoint at the moment it's examined. Runs in Θ(V+E). Undirected graphs only ever produce tree/back edges.

5. Topological sort

Think of baking a cake: the batter must be mixed before it goes in the oven, the cake must cool before it is frosted — some tasks have a hard "must come before" rule (a directed edge), others are independent (any order works, e.g. cracking the eggs vs. measuring the flour). A topological sort is any full ordering of all the tasks that respects every "must come before" rule. It only makes sense for a graph with no cycles (a DAG, directed acyclic graph) — if task A must come before B, and B must come before A, no valid order exists at all.

topologicalSort is beautifully short: run DFS to get every vertex's finish time, then list vertices in decreasing order of finish time. The first example is a baking DAG with nine items: flour, eggs and sugar go into the batter, the batter and the oven go into the bake, the bake leads to cooling and cooling to frosting, sugar also goes straight into the frosting — and the plates have no rule attached to them at all (an isolated vertex). DFS scans the vertices in the order listed, so the finish times are batter 2/9, flour 1/10, eggs 11/12, sugar 13/14 and so on, and the final list is plates, oven, sugar, eggs, flour, batter, bake, cool, frost.

Try your own DAG. Use u->v edges (a directed graph is required — topological order is meaningless for an undirected graph).

topologicalSort in Dart

“Put each finishing vertex at the front of a list” is the same as reading the finish order backwards, so we reverse the list once instead of inserting at the front (insert(0, x) would cost O(n) each time).

The back-edge lemma (acyclic ⇔ no back edge) as code, cross-checked against Kahn’s in-degree algorithm, an independent method:

Input size → what is feasible: V, E ≤ 10⁵ → Θ(V+E) ≈ 3·10⁵ steps, instantaneous; the baking example has V = 9, E = 8.

Why "decreasing finish time" works. Back-edge lemma: a directed graph is acyclic if and only if a DFS of it produces no back edge (a cycle would force the first-discovered vertex on it to eventually see a back edge from one of its own descendants, by the white-path theorem; conversely a back edge (u,v) means v is an open ancestor of u, so the tree-path v→u plus the edge (u,v) is a cycle). Given that, for EVERY edge (u,v) in a DAG, v can never be gray when (u,v) is examined (that would be a back edge, impossible in a DAG) — so v is either still white (tree edge: u finishes strictly after v, since u's dfsVisit call is still open when v's already returned) or already black (forward/cross: v finished before u even reached this edge). Either way, f[v] < f[u] for every edge (u,v) — which is exactly the definition of a valid topological order when read in decreasing finish-time order.

Running topologicalSort on a graph WITH a cycle silently produces a list that violates at least one edge's ordering — DFS still finishes normally (it doesn't get stuck), it just produces back edges, and the "decreasing finish time" guarantee depended entirely on the graph having none. Always check for a cycle first (equivalently: check whether DFS produced any back edge) before trusting a topological-sort result.

topologicalSort(G): run dfs(G) for finish times, then list vertices in decreasing order of finish time. Only defined for a DAG. Runs in Θ(V+E) (dominated entirely by the dfs call).

6. Strongly connected components (Kosaraju's algorithm)

In a one-way-street city, two intersections are "mutually visitable" if you can drive from A to B AND from B to A (possibly via completely different streets). A strongly connected component (SCC) is a maximal group of intersections that are all mutually visitable with each other. Every vertex belongs to exactly one SCC (its own private one, if nothing else).

The algorithm (credited to S. R. Kosaraju) is a clever trick using the graph's transpose G^T (every edge reversed — G and G^T always have IDENTICAL strongly connected components, since "A reaches B and B reaches A" is symmetric under reversing every edge). Run DFS on G, reverse the edges, then run DFS again on the reversed graph starting from the vertex that finished last:

Try your own directed graph. Use u->v edges.

stronglyConnectedComponents in Dart

The comments name the pseudocode lines. second.dfsVisit(root) grows one DFS tree of G^T; the vertices that finished during that call are exactly that tree, i.e. one SCC.

The finish-order lemma (the reason decreasing finish time works) as code: for every edge between two different components, the component of u has the later finish time.

Input size → what is feasible: V, E ≤ 10⁵ → two DFS passes + one transpose ≈ 6·10⁵ steps; the examples above have V ≤ 8, E ≤ 11.

Why the second DFS’s decreasing-finish-time order works. Write f(C) for the latest finish time of any vertex in an SCC C. Finish-order lemma: if G has an edge (u,v) from u ∈ C to v ∈ C′ (two different SCCs), then f(C) > f(C′). Why: if DFS enters C first, at that moment every vertex of both components is white and reachable through white vertices, so by the white-path theorem the first vertex of C becomes an ancestor of everything in C′ too and finishes last. If it enters C′ first, no path leads back from C′ to C (otherwise they would be one SCC), so all of C′ finishes while C is still untouched. Either way the component the edge starts from has the larger f. Reversing every edge flips this: an edge from C to C′ in G^T means f(C) < f(C′). The second DFS always starts at the unvisited vertex with the largest f, so it starts in a component whose G^T edges can only lead into components with a larger f — and those are already finished. The new tree therefore cannot leak out: it is exactly one SCC.

Why skipping the transpose fails. A tempting shortcut: run the second DFS on G itself and scan the vertices in increasing order of first-pass finish times. This is wrong in general. Counterexample: edges p->q, q->p, p->r, r->s. The first DFS from p (with adj[p] = [q, r]) gives f[q]=3, f[s]=6, f[r]=7, f[p]=8. Scanning q first in G follows q→p→r→s and swallows all four vertices into one tree, but the real components are {p,q}, {r} and {s}. The transpose is essential, not an implementation detail.

stronglyConnectedComponents(G): (1) dfs(G), record finish times; (2) compute G^T; (3) dfs on G^T, visiting vertices in DECREASING order of step-1 finish times; (4) each resulting DFS tree = one SCC. Runs in Θ(V+E) — two DFS passes plus building the transpose.

Quiz

Interview questions

Cheat sheet

Algorithm	Time	Space	Requires	Gives you
bfs	O(V+E)	O(V)	any graph	fewest-edges distance & shortest-path tree from a source
printPath	O(path length)	O(path length) recursion	a computed parent array (e.g. from BFS)	the actual vertex sequence of a path
dfs / dfsVisit	Θ(V+E)	O(V)	any graph	discovery/finish times, DFS forest, edge classification
topologicalSort	Θ(V+E)	O(V)	a DAG (directed, acyclic)	a linear order respecting every "must come before" edge
stronglyConnectedComponents	Θ(V+E)	O(V+E) (for G^T)	a directed graph	every maximal mutually-reachable vertex group

"Cycle exists?" = "does dfs(G) produce a back edge?" (back-edge lemma). "Is this DAG's order valid?" = check every edge goes from an earlier to a later position. "Are u,v in the same SCC?" = does u reach v AND v reach u?