AlgoScope

Graph Traversal

Visit everything you can reach, once, and let the order you take vertices out of the frontier decide the shape of the search.

9 topics3 lessons1 families

A graph is a set of vertices and the edges between them. It has no order and no root, so traversal is the act of imposing one: start somewhere, keep a set of vertices you have seen, and keep pulling from a frontier of vertices you have reached but not yet expanded.

The only real decision is which vertex to pull next. A queue takes the oldest, so the search grows in rings and reaches every vertex by the fewest edges. A stack, usually the call stack, takes the newest, so the search runs down one path until it dead-ends and then backtracks. Either way each vertex is expanded once and each edge is looked at once from each end, which is the O(V + E) on every cost line here.

Everything else in this category is a few lines added to one of those two loops: a component number written down on each visit, a colour that has to alternate across every edge, a note of which vertices are still on the current path. The memory is O(V) for the seen set and the frontier, and on a grid the frontier can hold a whole row, which is where the r * c bounds come from.

After this you can

  • Write BFS and DFS over an adjacency list and say which one a question needs
  • Explain why BFS gives the fewest-edge path and DFS gives no distance guarantee at all
  • Count connected components in a graph, and the same thing on a grid with flood fill
  • Detect a cycle, and say why the undirected test and the directed test are different tests
  • Replace a recursive DFS with an explicit stack when the depth would overflow
001121345u

Dequeue 0, distance 0. Its adjacency list: 1, 2. New: 1, 2, each at distance 1, enqueued.

Open in the player →or start at step 2

In this order

  1. Breadth-First SearchExplore layer by layer with a queue; discovers shortest paths in unweighted graphs.
  2. Depth-First SearchGo as deep as possible before backtracking; the recursion stack is the frontier.
  3. DFS RecursiveThe natural recursive form; each call frame is one vertex, and the current path is the call stack.
  4. DFS IterativeExplicit stack of vertices; avoids recursion depth limits.
  5. Connected ComponentsRun BFS or DFS from every unvisited vertex; each run colours one component.
  6. Flood FillBFS or DFS on a grid, treating same-coloured neighbours as edges.
  7. Number of IslandsCount connected components on a grid with flood fill from every unvisited land cell.
  8. Cycle DetectionUndirected: an edge to a seen vertex other than the parent. Directed: an edge to a vertex still on the DFS path.
  9. Bipartite CheckTwo-colour the graph with BFS; an edge between two vertices of the same colour means an odd cycle.

Where people go wrong

Marking visited on pop instead of on push

Mark a vertex the moment it enters the frontier. If you wait until it comes out, a vertex with three edges into it is queued three times and expanded three times, and the traversal stops being linear.

The parent check in undirected cycle detection

Every undirected edge is stored twice, so the edge you arrived on always leads back to a vertex you have seen. Skip the parent, but skip one edge to it, not all of them: a second parallel edge to the parent really is a cycle.

Using BFS on a weighted graph

BFS counts edges, not weight. A two-edge route with weights 9 and 9 is found before a five-edge route of weight 1 each, so the answer is the wrong path with the wrong cost.

Or a different category

Shortest Path

Edges carry weights and you want the cheapest route rather than the one with the fewest edges.

Connectivity and Topological Order

You need a topological order, strongly connected components, or the single edge whose removal would split the graph.

Lessons that teach these