Breadth-first and depth-first

Two ways to walk a graph, identical except for which container holds what you have not visited yet — and that one difference decides what you find first.

#The same graph, two walks

A small social graph, starting from you:

###   BFS: [you, ana, bo, cy, di, ed, fay, zoe]
###   DFS: [you, ana, di, zoe, bo, ed, cy, fay]

BFS takes everyone one step away, then everyone two steps away. ana, bo, cy — all your direct friends — before any friend-of-a-friend.

DFS commits to a path and follows it to the end: ana, then ana's friend di, then di's friend zoe, before it ever looks at bo.

Notice zoe. DFS found her fourth; BFS found her last. If the question were "find zoe", DFS won. If the question were "how far away is zoe", only BFS can answer.

#The only real difference

// BFS — a queue
Deque<String> q = new ArrayDeque<>();
q.add(start);
while (!q.isEmpty()) {
    String v = q.poll();              // oldest first
    for (String n : neighbours(v)) if (seen.add(n)) q.add(n);
}
 
// DFS — a stack
Deque<String> st = new ArrayDeque<>();
st.push(start);
while (!st.isEmpty()) {
    String v = st.pop();              // newest first
    ...
}

poll against pop. Everything else is the same, which is why they are taught together and why ArrayDeque is the right container for both — the collections course's point about it doing both ends in O(1).

DFS also has a recursive form, and that is the more common way to write it. Its stack is the call stack, which means the previous lesson's ceiling applies: recursive DFS on a graph a hundred thousand deep overflows, and the iterative version does not.

#What each one is for

BFS finds the shortest path — but only when every edge costs the same. That is the guarantee, and the condition is easy to forget. Because BFS reaches everything at distance 1 before anything at distance 2, the first time it sees a vertex is by a shortest route.

Put weights on the edges and that breaks immediately: a two-hop path can be cheaper than a one-hop path. Then you need Dijkstra, which is BFS with a PriorityQueue instead of a queue — take the cheapest frontier vertex rather than the oldest. The shape is so similar it is worth seeing as one algorithm with a different container.

DFS is for exhausting a structure, and for questions about whether a path exists rather than how long it is:

• cycle detection
• topological sort (build order, bean creation order)
• connected components
• backtracking, which is DFS over a tree of choices

#The visited set is not optional

Both loops above call seen.add(n) before enqueueing. Without it, a graph with any cycle loops forever — and seen must be checked when you enqueue, not when you dequeue, or the same vertex is added many times before it is first processed.

Worth noting that this makes the traversals O(V + E): every vertex enters the container once, and every edge is looked at once.

#Choosing

The last two rows are the practical ones. BFS holds an entire frontier in memory, which for a wide graph can be enormous. DFS holds one path, which is cheap — and can wander very deep down a branch that has no answer.