The formula (the core equation(s), each with a one-line reading of what it says)
Traversal has two canonical forms, and the only difference between them is the container that holds the work you haven't done yet.
BFS: frontier is a queue (first in, first out)
DFS: frontier is a stack (last in, first out)
Reads: BFS finishes everything one hop away before touching anything two hops away; DFS commits to a branch and follows it to the end before backing up.
Visited rule: mark v the first time you see it; never enqueue or push a marked vertex again
Reads: the entire correctness of both algorithms lives in this one line — it is what turns "wander the graph" into "terminate on the graph."
BFS distance invariant: dist(v) = dist(u) + 1
where u is the vertex that first discovered v
Reads: BFS hands you the minimum hop count from the start to every reachable vertex, for free, as a side effect of the queue's ordering.
Cost: time O(|V| + |E|), space O(|V|)
Reads: every vertex gets touched once and every edge gets examined once — linear in the size of the network, which is as cheap as any complete answer can be.
Reachability: v is connected to s <=> a traversal started at s marks v
Reads: connectivity is not a property you inspect; it is the output of running the walk.
Where you meet it (2-4 concrete engineering situations, specific: bench, test stand, review board)
Continuity on a harness or a board. A netlist is a graph: pins are vertices, wires and traces are edges. "Is J3-7 electrically common with the chassis ground lug" is a traversal question — flood outward from one node and see whether the other one gets marked. Every ECAD tool's net extraction and every design-rule shorts check runs exactly this walk, and the autorouter placing the trace in the first place is running breadth-first wave expansion across the board grid.
Fault tracing on the test stand. One signal conditioner drops out mid-run. Which channels in the data package are now suspect? Draw the signal flow as a directed graph — supply feeds conditioner, conditioner feeds mux, mux feeds DAQ — and traverse downstream from the failed box. Everything the walk marks is contaminated; everything it doesn't is defensible in front of the customer. Doing this by eyeball on a 400-channel stand is how good data gets thrown out with bad.
The FMEA and fault-tree review. "Can this single failure propagate to loss of the top-level function" is a reachability query on the fault graph. A review board arguing about it from memory is doing a traversal badly; a script doing it from the model does it completely, including the sneak path through the shared power bus nobody drew on the whiteboard.
Bus and network discovery. Walking an Ethernet switch fabric, a 1553 bus architecture, or a software dependency tree to enumerate what's actually attached is a traversal with the visited set doing the real work — without it, the first loop in the topology turns your discovery script into a space heater.
How it works (the real substance — behavior, gotchas, limits of validity, the mistake people make)
Take eight nodes in a ring, 0 through 7, each wired to its neighbors, plus one jumper straight across from 0 to 4. Start both algorithms at node 0 and ask for node 4. BFS discovers node 4 at distance 1 — the queue processes all of node 0's neighbors (1, 7, and 4 via the jumper) before anything else, so the jumper wins immediately. A DFS that happens to try neighbor 1 first walks 0-1-2-3-4 and reports a path of 4 edges. Both answers are correct — node 4 is reachable either way — but only the BFS answer is shortest. That is the first thing to internalize: reachability is the same for both; distance is a BFS-only guarantee.
The mistake people make follows directly. Someone uses DFS because the recursive version is five lines, then reads the path length off the result and calls it the distance. It isn't. DFS path length depends on the arbitrary order neighbors happen to be stored in, and on a big graph it can be spectacularly long. If the question contains the word "shortest," the container must be a queue. And one more boundary: BFS minimizes hop count, not weighted cost. The moment edges carry unequal weights — cable lengths, link delays, resistances — shortest-hops and shortest-cost part company, and the right tool becomes Dijkstra's algorithm, which is BFS with the queue upgraded to a priority queue.
The second gotcha is memory, and it cuts opposite ways. BFS holds an entire frontier at once: on a branching structure that fans out by 10 per level, the frontier at depth 6 is 10⁶ — a million entries in the queue. DFS holds only the current branch — memory proportional to depth, not width — which is why it's the default for deep searches. But the recursive DFS everyone writes carries its state on the call stack, and a graph with a path a few hundred thousand vertices long will blow the stack limit on most runtimes. Production DFS uses an explicit stack for exactly this reason.
Third: the visited set is not an optimization, it is the algorithm. Drop it and any cycle — and real networks are full of them, ground loops, redundant buses, bidirectional links — recycles the walk forever. Every "my discovery script hung" story is this story.
The cost is honest and flat: O(|V| + |E|). A network of a million vertices averaging four connections each is roughly 10⁶ + 4·10⁶ = 5·10⁶ edge examinations — milliseconds on anything modern. Traversal does not get cheaper than linear, and it never needs to be, because you cannot certify reachability without looking at least once at everything reachable.
History (who derived it and when, told as a short story with inline [n] citations)
Depth-first search was invented by a man walking through an actual maze. Charles Pierre Trémaux, a French telegraph engineer and École Polytechnique alumnus, worked out a guaranteed maze-escape procedure — mark each passage entrance as you use it, never take a passage marked twice, prefer unmarked ones — and the method reached print in Édouard Lucas's 1882 Récréations Mathématiques [2][6]. Strip away the chalk marks and Trémaux's rules are depth-first search with a visited set: commit to a corridor, back out when it dead-ends, never re-explore.
Breadth-first search arrived by a different door, twice, for practical reasons both times. In 1959 Edward F. Moore published "The Shortest Path Through a Maze" in the proceedings of the Harvard International Symposium on the Theory of Switching, using level-by-level expansion to find not just a way out but the shortest one [1][5]. Two years later C. Y. Lee published "An Algorithm for Path Connections and Its Applications" in IRE Transactions on Electronic Computers, turning the same wave expansion into a wire-routing method for circuit boards [1][4]. The Lee router — flood outward from the source pad, backtrack along decreasing labels from the target — is BFS wearing safety glasses, and its descendants still route boards today.
The modern, general form belongs to Robert Tarjan, whose 1972 paper "Depth-first search and linear graph algorithms" in the SIAM Journal on Computing showed that DFS was not just a maze trick but a machine for solving whole families of graph problems — strongly connected components, biconnected components — in linear time [2][3]. Tarjan and John Hopcroft used the same machinery to build the first linear-time planarity test, and in 1986 the two shared the ACM Turing Award "for fundamental achievements in the design and analysis of algorithms and data structures" [7][8]. From a telegraph engineer's chalk marks to the Turing Award: the walk itself never changed, only what people noticed it could carry.
Sources
- https://en.wikipedia.org/wiki/Breadth-first_search
- https://en.wikipedia.org/wiki/Depth-first_search
- https://epubs.siam.org/doi/10.1137/0201010
- https://en.wikipedia.org/wiki/Lee_algorithm
- https://books.google.com/books/about/The_Shortest_Path_Through_a_Maze.html?id=IVZBHAAACAAJ
- https://www.cantab.net/users/michael.behrend/repubs/maze_maths/pages/lucas_ch3_en.html
- https://en.wikipedia.org/wiki/Robert_Tarjan
- https://amturing.acm.org/award_winners/tarjan_1092048.cfm