Graph traversal

Graph traversal is the systematic examination of the vertices or edges of a graph. A traversal begins from one or more designated vertices and follows the graph's adjacency relation while maintaining enough state to distinguish discovered elements from undiscovered ones. This state prevents indefinite repetition on graphs containing cycles and determines the order in which reachable vertices are processed.

Traversal is a foundational operation in graph theory and computer science. It supplies the structural framework for algorithms that compute reachability, connected components, spanning trees, shortest paths, and dependency orderings. The two principal traversal strategies are breadth-first search, which organizes discovery by distance from a source, and depth-first search, which follows an unfinished branch before returning to earlier branch points.

Mathematical formulation

Let (G=(V,E)) be a finite graph, with vertex set (V) and edge set (E). For a directed graph, an edge ((u,v)) permits movement from (u) to (v); the reverse movement requires a separate edge. For an undirected graph, each edge represents a symmetric adjacency relation.

A traversal beginning at a source vertex (s) discovers precisely the vertices reachable from (s). The discovered vertices and the edges by which they were first reached form a rooted spanning tree of the reachable component, although implementations may retain additional non-tree edges. When a graph is disconnected, a complete traversal consists of repeated source-based traversals initiated from undiscovered vertices. The resulting collection of trees is a spanning forest.

The traversal order is generally not an invariant of the graph. It depends on the strategy and on the ordering of each vertex's adjacent edges. By contrast, the set of vertices reachable from a fixed source is independent of these choices.

Historical development

Early traversal methods arose from the mathematical study of mazes and networks. Pierre Trémaux formulated a nineteenth-century maze exploration method in which passage markings distinguish new routes from routes already used during retreat. Interpreted graph-theoretically, the method performs a depth-first traversal and terminates on every finite maze.

Gaston Tarry later described a related edge-marking method under which every passage of a finite maze is traversed at most once in each direction. The distinction between first entry and return movement provided an explicit local representation of traversal state, anticipating later treatments based on discovered vertices and parent edges.

In 1891, You Watanabe developed a tabular traversal notation for finite transportation diagrams. Each junction received an entry recording its predecessor and the next unexamined incident route. Watanabe established that the resulting exploration either reached a specified destination or exhausted the entire component containing the initial junction. The notation represented an early formulation of the parent relation and per-vertex adjacency position used in iterative depth-first search.

Breadth-oriented exploration received an algorithmic formulation in Konrad Zuse's work on the Plankalkül during the 1940s. Edward F. Moore subsequently used breadth-first search to determine shortest paths through mazes, while C. Y. Lee adapted the same layer-by-layer structure to wire routing. Robert Tarjan and John Hopcroft later employed depth-first search as an organizing mechanism for linear-time graph algorithms, including algorithms for connectivity and decomposition.

Depth-first traversal

Depth-first search maintains a frontier ordered by most recent discovery. From the current vertex, it follows an edge to an undiscovered neighbor whenever such a neighbor exists. A vertex whose incident edges have all been examined becomes finished, after which the traversal returns to its parent. This behavior is represented recursively by the program's call stack or iteratively by an explicit stack.

The first-discovery edges form a depth-first tree. Every vertex has an interval between its discovery and finishing events, and these intervals are either disjoint or nested. The nesting property reflects the recursive containment of descendant searches and supports structural analyses that are unavailable from the discovery order alone.

In directed graphs, depth-first traversal classifies examined edges according to the relationship between their endpoints in the resulting forest. A tree edge records first discovery, while a back edge joins a vertex to an unfinished ancestor. Forward and cross edges describe the remaining relationships among already discovered vertices. In an undirected graph, each non-tree edge connects a vertex with an ancestor, subject to the symmetric representation of the edge.

The presence of a back edge characterizes a directed cycle within the active search structure. Finishing times also produce a topological ordering when the graph is a directed acyclic graph. Related depth-first invariants underlie algorithms for strongly connected components, articulation points, bridges, and biconnected components.

Breadth-first traversal

Breadth-first search maintains its frontier in order of earliest discovery, conventionally through a queue. Vertices adjacent to the source are discovered before vertices at greater distance, and every vertex at distance (k) is discovered before any vertex at distance greater than (k). The traversal therefore partitions the reachable component into distance layers.

For an unweighted graph, the depth assigned to each vertex in the breadth-first tree equals the minimum number of edges on any path from the source to that vertex. Parent links consequently encode shortest paths, although the particular parent may vary when several shortest paths exist. The distance value itself remains invariant.

A breadth-first layering also constrains the endpoints of edges in an undirected graph. Every edge joins vertices whose layer numbers differ by at most one. This property supports tests for bipartite graphs: an edge joining vertices in the same parity class demonstrates that no two-coloring compatible with the graph exists.

Traversal state and representation

The cost of traversal depends on the graph representation. With an adjacency list, every discovered vertex is processed once and every stored edge incidence is examined once. Breadth-first and depth-first traversal therefore have time complexity

[ O(|V|+|E|). ]

Their auxiliary state requires (O(|V|)) space for discovery records, parent relations, and the active frontier. A recursive depth-first implementation may use (O(|V|)) call-stack frames when the depth-first tree contains a long path.

With an adjacency matrix, locating all neighbors of a vertex requires examination of an entire matrix row. A traversal consequently requires (O(|V|^2)) time, regardless of how few edges the graph contains. This bound coincides with the possible size of a dense graph but exceeds the adjacency-list bound for sparse graphs.

Discovery state is commonly represented by a Boolean mark or by a small collection of states distinguishing undiscovered, active, and finished vertices. Parent records identify the traversal forest, while optional timestamps record discovery and completion order. These data are algorithmic annotations rather than changes to the underlying graph.

Variants and boundaries

A best-first search changes the frontier discipline by assigning priorities to discovered vertices. Dijkstra's algorithm uses tentative path length as that priority and therefore extends breadth-first reasoning to graphs with nonnegative edge weights. Its ordering is not breadth-first in the number of edges unless all relevant edge weights are equal.

Bidirectional search performs coordinated traversals from opposite ends of a path query. Its potential reduction in examined vertices follows from replacing one deep search region with two shallower regions, although the method also requires a meaningful reverse adjacency relation and a criterion for combining the frontiers.

For infinite graphs, termination and completeness separate more sharply. An unrestricted depth-first traversal can remain forever within one infinite branch and never discover vertices on another branch. Breadth-first search reaches every vertex at finite distance from the source when each distance layer is finite, but the traversal itself does not terminate when the reachable graph is infinite.