Graph: BFS and DFS

Two ways to explore everything reachable from a starting point.

The idea (a rumor in a town, or a maze)

A graph is dots (nodes) joined by lines (edges): cities and roads, people and friendships. To explore it you need a to-do list of nodes still to look at, and a note of the ones you have already seen (so you never go in circles).

The code is almost identical. Only the to-do list (queue vs stack) changes the order.

Watch it work

Nodes are numbered 0, 1, 2, ... with no gaps (at most 10 nodes, 15 edges). Neighbors are visited in increasing order.

Try it

Common mistakes

Complexity, in plain English: each node is handled once and each edge is looked at a constant number of times, so the work grows with nodes plus edges (O(V + E)). The to-do list can hold up to all nodes, so extra memory is O(V).