loading
loading
loading
loading
Two ways to visit every reachable node in a graph — breadth-first spreads outward level by level, depth-first commits to one path and backtracks — and the queue-vs-stack choice that produces each one.
A graph is a set of nodes connected by edges — trees, grids, and networks are all special cases. Traversal means systematically visiting every node reachable from a start node, and there are exactly two orders that matter: breadth-first search (BFS) explores in expanding rings, one edge farther out each round, using a queue; depth-first search (DFS) commits to one path as deep as it goes before backtracking, using a stack (explicit or the recursive call stack). Both visit every reachable node exactly once, both run in O(V + E), and both use O(V) extra space — the only real difference is the order nodes come out, which is entirely a consequence of which end of the frontier you remove from.
Step through graph traversal (bfs & dfs) live, one move at a time — this becomes a fully interactive visualizer.
Coming soonvisited (nodes already processed, so you never revisit one) and a frontier of nodes discovered but not yet processed.function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
const distance = { [start]: 0 };
while (queue.length > 0) {
const node = queue.shift(); // FIFO: oldest discovered goes first
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
distance[neighbor] = distance[node] + 1;
queue.push(neighbor);
}
}
}
return distance; // fewest-edges distance from start to every reachable node
}function dfs(graph, node, visited = new Set()) {
if (visited.has(node)) return visited;
visited.add(node);
for (const neighbor of graph[node]) {
dfs(graph, neighbor, visited); // commits to this branch before trying the next
}
return visited;
}function dfsIterative(graph, start) {
const visited = new Set();
const stack = [start];
while (stack.length > 0) {
const node = stack.pop(); // LIFO: most recently discovered goes first
if (visited.has(node)) continue;
visited.add(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) stack.push(neighbor);
}
}
return visited;
}| BFS | DFS | |
|---|---|---|
| Frontier structure | Queue (FIFO) | Stack (LIFO) or recursion |
| Exploration shape | Expanding rings, level by level | One path deep, then backtrack |
| Shortest path (unweighted) | Guaranteed — first visit is fewest edges | Not guaranteed |
| Memory pattern | Can hold a whole wide level at once | Holds one path's worth of nodes |
| Typical use | Shortest path, level-order, "nearest" queries | Cycle detection, topological sort, backtracking, connectivity |
| Natural implementation | Iterative with an explicit queue | Recursive (implicit stack) or iterative with an explicit stack |
A queue only ever gives back what went in longest ago. The start node's neighbors (distance 1) are enqueued first, so they're all dequeued — and their own neighbors (distance 2) enqueued — before any distance-2 node gets a turn. That FIFO discipline is the entire mechanism behind BFS's expanding-ring shape: it isn't a special graph algorithm, it's a generic traversal with a queue for a frontier.
A stack always gives back what went in most recently. The moment a node's first neighbor is pushed, that neighbor — not any of the start node's other neighbors — is the very next thing popped and explored. The search keeps chasing the newest discovery down one branch until it hits a dead end (no unvisited neighbors left to push), at which point popping naturally returns to the most recent unexplored branch point. Recursion produces the identical order because the call stack *is* a stack.
Any time "fewest steps" or "nearest" matters in an unweighted graph — shortest path between two people in a social graph, minimum moves to solve a sliding puzzle, nearest available node in a network. BFS's guarantee (first visit = fewest edges) makes it the correct choice; DFS gives no such guarantee and can return a needlessly long path.
Anything that needs to fully explore one possibility before trying the next: detecting a cycle (does following edges ever lead back to a node already on the current path?), topological sort (order tasks so every dependency comes first — a direct application of DFS finishing order), connected-components / flood fill, and backtracking search (mazes, Sudoku, permutations) where the algorithm needs to commit, fail, and unwind.
Both BFS and DFS assume every edge costs the same — that's exactly why BFS's fewest-edges guarantee equals shortest-*weighted*-path only when weights are uniform. Once edges have different weights, fewest edges no longer means lowest total cost, and the right tool becomes Dijkstra's algorithm (or A* with a heuristic) — a frontier ordered by *accumulated cost* using a priority queue instead of a plain queue. It's the same expanding-frontier idea from BFS, generalized past uniform weights.
A graph can have cycles — without marking nodes visited and skipping them, a traversal can loop forever re-discovering the same nodes through a cycle. Trees never have this problem (no cycles by definition), which is why simpler tree traversals can skip the visited check. Every graph traversal needs it.
State up front which structure you're using for the frontier and why — that single sentence proves you understand BFS and DFS are the same algorithm shape with a different frontier, not two unrelated procedures to memorize. Watch for: directed vs undirected (does an edge imply a return edge?), disconnected graphs (a single traversal from one start node won't reach every node — you may need to loop over all nodes and traverse from any unvisited one), and always initialize the visited set before starting, not after popping, or the same node can be enqueued/pushed multiple times.
Recursion is one way to implement DFS — the call stack acts as the stack — but an explicit iterative stack works identically and avoids recursion-depth limits on very deep graphs. Both produce the same LIFO exploration order.
Only if you skip the visited set. A cyclic graph without one will re-enqueue/re-push nodes forever. Marking a node visited the moment it's discovered (not when it's processed) prevents this and also prevents duplicate frontier entries.
Only when every edge has the same weight (or is unweighted). BFS guarantees fewest *edges*, which equals shortest path only under uniform weights. For weighted graphs, use Dijkstra's algorithm instead.
The Pathfinding Visualizer runs BFS on an unweighted grid — exactly the algorithm described here, applied to a maze instead of an abstract graph. Every grid cell is a node, and adjacency is up/down/left/right movement.
Share what clicked for you and see notes from other learners on this topic.
Coming soon