This site's Graph Traversal category holds eleven entries, and four of them are the same base traversal wearing progressively more bookkeeping. Depth-First Search's own Pitfalls section says so directly: "DFS on a directed graph unlocks two more classic uses. Track which nodes are still 'on the current path' versus fully finished (not just visited-or-not) and DFS can detect a cycle... Push each node onto a stack the moment it finishes, then reverse that stack at the end, and you get a topological sort... Both are the same traversal as this maze, just with directed edges and one extra bit of bookkeeping per node." Strongly Connected Components layers one more piece of bookkeeping on top of that, and Articulation Points and Bridges reuses that exact layer turned on an undirected graph instead. Three entries break from that family entirely, each in a different way. Eulerian Path / Circuit isn't a DFS variant at all, and its own opening paragraph is careful to distinguish itself from a different site entry, not from anything in this category. 2-SAT breaks even further: it doesn't start life as a graph at all, only becoming one once a boolean formula's clauses are translated into implications, and it reuses Strongly Connected Components wholesale rather than adding any bookkeeping of its own. Floyd's Cycle Detection breaks from the family a third way: it doesn't use a stack, queue, or visited set at all, because the graph it walks — every node with exactly one outgoing edge — never branches, so two plain pointers moving at different speeds are enough. This guide is a funnel of seven questions, starting from the one property (shortest path) that pulls a visitor straight to BFS before any DFS bookkeeping is even relevant.
Breadth-First Search. Its own opening paragraph states the mechanism plainly: "visit a node, enqueue its unvisited neighbors, repeat... every node one step away from the start gets processed before any node two steps away, which is exactly what 'process the graph one distance-from-start layer at a time' means. That layer-by-layer order is also what guarantees BFS finds the shortest path in an unweighted graph — the first time it reaches a node is provably via the fewest possible steps." Nothing else in this category makes that guarantee; swap the queue for a stack and, per DFS's own Pitfalls section, "DFS answers a different question — 'is anything reachable, and what does one path look like' — not 'what's the shortest path.'" If shortest-path-by-edge-count isn't the question, none of the rest of this category needs a queue at all — every remaining entry below is stack-based, one way or another. Two refinements are worth knowing about even once BFS is the right family of answer. If the graph has real branching and the two endpoints are far apart, Bidirectional Search keeps BFS's exact shortest-path guarantee while growing two smaller search circles — one from each end — instead of one big one, at real (measured on this site: up to two orders of magnitude on a sparse 50,000-node graph) cost savings. If instead it's memory that's the constraint — a state space too large to hold a full BFS frontier in — Iterative Deepening DFS gets the identical shortest-path guarantee back from a completely different direction: repeated depth-limited DFS passes, one deeper limit at a time, each needing only a single stack instead of a whole frontier. Its own Pitfalls section is blunt about the cost: on its demo maze this trades an 8.95x increase in total node-visits for that memory bound, "not a strictly better BFS" but a real trade worth making only when memory, not time, is the scarce resource.
Eulerian Path / Circuit (Hierholzer's Algorithm). This is the one entry in the category that isn't a DFS extension at all — it doesn't track discovery time, low-link values, or a three-state visited flag, because the question it answers has nothing to do with reaching every vertex once. Its own opening paragraph draws the real contrast, and it isn't against anything else on this page: "Easy to confuse with Hamiltonian path / cycle, which asks the mirror-image question about vertices instead — visit every vertex exactly once, edges are just how you move between them. The two problems look like siblings but aren't: Hamiltonian path has no known efficient test and needs backtracking search even to decide whether an answer exists at all; Eulerian path has an exact one-line existence test and, when one exists, finding it takes linear time — no search, no guessing, no backtracking." Hierholzer's algorithm does walk an explicit stack, the same surface shape as the iterative traversals below — but what it pushes and pops is "vertices still owed a finished visit," not "vertices still being explored for the first time," and nothing about it generalizes to the directed-order or component questions the rest of this funnel asks. If covering every edge isn't the job, this is the only entry the rest of the funnel rules out for good — everything past this point really is DFS, or DFS with one extra layer.
Floyd's Cycle Detection (Tortoise and Hare). Every other entry in this category allows a node to have several outgoing edges and spends O(V) memory on a visited set precisely because a branching graph needs to remember which branches are already explored. A node with exactly one outgoing edge — the defining shape of a linked list, or any "apply this function to get the next state" chain — never branches, so there's nothing a visited set would tell a slower, one-pointer walk that a second, faster pointer can't reveal just by catching up to it: its own Why It Works section proves a fast pointer gaining one position per step on a slow one is guaranteed to meet it within one lap of any cycle, no bookkeeping required. That guarantee doesn't generalize to a graph with real branching — this is the one entry in the category where the answer to "how much can this node branch" isn't "however much the input graph branches," it's "not at all, by definition of the question being asked."
Two entries, both a plain DFS with bookkeeping added, and both only make sense on a directed
graph. A valid order to do everything in, or a check for whether one exists at
all: Topological Sort. Its own opening
paragraph names the mechanism directly: "It's built directly on depth-first search: run a DFS from
every node, and every time a node finishes... push it onto a stack. When there's nothing left to
visit, reverse that stack." The one addition over plain DFS is a third node state — not just
visited-or-not, but unvisited/visiting/done — and that same
three-state DFS answers cycle detection on its own, independent of wanting an order at all: its own
Pitfalls section calls this "the standard way to answer 'does this directed graph have a cycle at
all.'" Grouping every node with the full set of others it can reach and be reached by in
return: Strongly Connected
Components (Tarjan's Algorithm). Its own opening paragraph places it exactly one step past
Topological Sort: "Topological sort already showed that a three-state depth-first search... can tell
whether a directed graph has any cycle at all. Tarjan's algorithm asks a sharper question —
not just 'is there a cycle,' but 'group every node into exactly the set of other nodes it's mutually
reachable with' — and answers it with one more piece of bookkeeping layered onto that same single
DFS pass": a discovery time and a low-link value per node, where "the moment a node's low-link
equals its own discovery time, everything still sitting 'in progress' below it on an explicit stack
forms one complete SCC." Order-checking needs nothing past the three-state flag; grouping needs the
disc/low-link pair on top of it.
A second entry answers the same grouping question a different way: Strongly Connected Components (Kosaraju's Algorithm) trades the low-link bookkeeping for two plain DFS passes — one to record a finish order, one on the graph's transpose (every edge reversed) to actually group nodes, starting from whichever node finished last. Its own opening paragraph is explicit that this isn't a different problem, just a different route to the same answer: "Kosaraju's algorithm answers the exact same question a genuinely different way." Reach for Tarjan's version when the single-pass, lower-memory approach matters; reach for Kosaraju's when avoiding low-link bookkeeping entirely, at the cost of building and storing a second (transposed) copy of the graph, is worth more.
Articulation Points and Bridges
(Tarjan's Algorithm). This reuses Strongly Connected Components' exact disc/low-link bookkeeping,
not a new mechanism — its own opening paragraph says so outright: "Strongly Connected Components's
low-link bookkeeping already answers a question about how far back up an active DFS path a subtree
can reach. Turned on an undirected graph instead of a directed one, that same number
answers a sharper local question directly — no explicit stack, no closing components, just an
inequality checked the instant each child's exploration returns." The two tests it adds are read
straight off the same numbers SCC already computes: "For a non-root vertex u with DFS
child v: if nothing in v's subtree can reach back above u
(low[v] ≥ disc[u]), then u is... an articulation point. Tighten the
inequality by one (low[v] > disc[u], nothing reaches back to u at all,
not even tied with it) and the tree edge u–v itself is... a bridge." Same numbers,
undirected graph, two inequalities instead of a stack-popping close — the only entry in the category
that's specifically about single points of failure rather than order, grouping, or coverage.
2-SAT. Every other entry above starts from a graph someone
already handed you; this one starts from a set of clauses, each exactly two literals joined by
or, and only becomes a graph through a translation step — (a ∨ b)
contributes the implications ¬a → b and ¬b → a to an
implication graph with one node per literal. Once that translation is done, the actual work is
handed entirely to Strongly Connected
Components: its own opening paragraph explains the reuse directly, "the whole satisfiability
question collapses to: run SCC on the implication graph, and check whether any variable's two
literals landed in the same component." No new bookkeeping gets added on top of SCC the way
Articulation Points and Bridges adds two inequalities — 2-SAT's only contribution is the
translation step before SCC runs and a one-line reading of its output afterward. Reach for this
specifically when the actual problem is boolean constraint satisfaction with at most two literals
per clause; general satisfiability with three or more literals per clause has no known polynomial
algorithm at all; that's a different kind of problem, not a bigger version of this one.
Depth-First Search, plain, with none of the extra layers above. It's the base case this entire funnel builds on: no three-state flag, no discovery/low-link pair, no edge-covering requirement — just "visit a node, push its unvisited neighbors, repeat," guaranteed (per its own Why it works section) to "eventually visit every cell reachable from the start, because nothing is ever skipped, just deferred." Reach for the recursive form for its brevity, or the iterative form — the same one this category's other three DFS-based entries build their own explicit stacks from — when the graph might be deep enough to risk the recursive call-stack overflow that DFS's own Pitfalls section (and, downstream, SCC's and Articulation Points' own Pitfalls sections) each flag independently.
| Entry | What it needs beyond reachability | Graph type | Time | Reach for it when |
|---|---|---|---|---|
| Breadth-First Search | queue instead of stack — layer-by-layer order | directed or undirected | O(V + E) | shortest path by edge count, unweighted graph |
| Bidirectional Search | two BFS queues, one per end, alternating by frontier size | directed or undirected | O(V + E) | same as BFS, but branching factor is real and the endpoints are far apart |
| Iterative Deepening DFS | repeated depth-limited DFS, one deeper limit at a time — no queue at all | directed or undirected | O(b^d) | same as BFS, but the frontier itself doesn't fit in memory |
| Depth-First Search | nothing extra — plain visited flag | directed or undirected | O(V + E) | what's reachable, or one path, not necessarily shortest |
| Topological Sort | three-state node flag (unvisited/visiting/done) | directed (DAG) | O(V + E) | valid dependency order, or detect a directed cycle |
| Strongly Connected Components (Tarjan's) | discovery time + low-link value, explicit stack | directed | O(V + E) | group nodes that can all mutually reach each other |
| Strongly Connected Components (Kosaraju's) | two DFS passes + transpose graph, no low-link value | directed | O(V + E) | same grouping as Tarjan's, without low-link bookkeeping |
| Articulation Points and Bridges | same disc/low-link pair, turned undirected | undirected | O(V + E) | find cut vertices or cut edges — single points of failure |
| Eulerian Path / Circuit | not a DFS extension — explicit stack over edge usage | directed or undirected (this site: undirected) | O(V + E) | a walk covering every edge exactly once, not every vertex |
| 2-SAT | not a graph to start with — reuses SCC wholesale after translating clauses to implications | n/a (implication graph is directed) | O(V + E) | deciding satisfiability of two-literal boolean clauses |
| Floyd's Cycle Detection | no stack, queue, or visited set — two pointers at different speeds | functional graph (every node: exactly one outgoing edge) | O(n) time, O(1) space | detect/locate a cycle in a linked list or similar chain with no extra memory |