04 · Graph Traversal & Topology

BFS · DFS · topological sort · Tarjan SCC — same graph · four lenses on its structure.

Speed 4×

Build your graph in any panel: click empty space to add a node · drag from one node to another to add a directed edge (drop on the same node for a self-loop) · right-click a node to delete it (and its incident edges). Edits propagate to all four panels and auto-restart the run.

What you're watching

All four panels render the same graph structure (same nodes, same edges). They differ in the colouring each algorithm applies to the nodes once it finishes. Below each panel, result states the algorithm's output in a sentence — the BFS depth range, the DFS finish order, the topological order (or "cycle detected"), the SCC count and group sizes.

The four algorithms

BFS queue · O(V + E)

Layer-by-layer exploration. Colour each node by its BFS depth from the start (or its layer in its connected component, if the graph has multiple). Useful for finding shortest paths in unweighted graphs — and as the lens that reveals "how spread out" a graph is.

DFS stack / recursion · O(V + E)

Goes deep, then backtracks. Colour each node by its finish-time rank — the order in which DFS completed processing it. This is the foundation that topological sort and Tarjan SCC build on.

Topological sort DAG only · O(V + E)

Produces a linear ordering of the nodes such that every edge goes from earlier to later in the sequence. Implemented as DFS with post-order push — the topological order is the reverse of the finish order. Only defined on a DAG; if the graph contains a cycle, this panel turns red and reports "cycle detected — no topological order exists".

Tarjan strongly-connected components DFS + lowlink · O(V + E)

Finds maximal sets of nodes that are mutually reachable (strongly connected components). A DAG has one SCC per node; a cyclic graph has one or more multi-node SCCs. Each component gets a distinct colour; sizes are reported in the result line.

TRY THIS

Start with the seeded DAG (5 nodes, 5 edges, no cycles). Topological sort succeeds; Tarjan finds 5 single-node SCCs. Now add an edge from the rightmost node back to the leftmost (creates a cycle through all 5 nodes). Topological sort fails immediately; Tarjan groups all 5 nodes into one SCC.

Why these four are presented together

BFS and DFS are the two traversal primitives — every graph algorithm in this list (and many others) is a small modification of one of them. Topological sort is "DFS with post-order push." Tarjan SCC is "DFS with discovery-time + lowlink tracking." Seeing them on the same graph makes the family resemblance visible: each algorithm is the same skeleton with different bookkeeping.

What I learned writing this

The "colour by output" pattern is the right visual abstraction for graph algorithms. Animating step-by-step (like sorting or pathfinding) feels jittery on a graph because the camera doesn't move — instead, settle for "here's where each node ended up," coloured by the algorithm's verdict. That's much easier to read.
Tarjan's lowlink update is one-liner that does a lot of work. low[v] = min(low[v], idx[w]) on a back-edge propagates "the earliest ancestor any descendant of v can reach." Every other piece of the algorithm follows from that single rule.
Topological sort and Tarjan SCC look almost identical in code — both DFS, both yield on discover/finish. Their outputs diverge only because Tarjan's stack/lowlink groups SCCs while topo's post-order push gives a sequence.
Building the graph by mouse is harder than expected. Distinguishing "click empty" from "drag from node to node" needs a small movement threshold (5px) plus mousedown-target tracking. Without the threshold, every click misregisters as a micro-drag; without target tracking, drag-from-empty creates ghost edges.

← Back to all algorithms