Graphs: BFS and DFS

Overview

Introduces graph representations and the two fundamental traversals.

A graph is a set of vertices and edges. An adjacency list stores, for each vertex, the vertices it connects to; it is compact for sparse graphs.

Breadth-first search explores in rings from the start and finds shortest paths in unweighted graphs. Depth-first search follows one path as far as possible and underlies cycle detection and topological ordering.