Graph traversal

Graph traversal is the systematic visiting of all nodes and edges in a graph, typically for the purpose of labeling, collecting, or transforming the structure rather than finding a specific target. Unlike graph search, which seeks a path or goal state, traversal is exploratory: its objective is coverage, not targeting. The canonical traversal algorithms are breadth-first search and depth-first search, each of which produces a spanning tree that reveals the graph's connectivity and hierarchical structure.

Traversal is the foundational operation of network analysis, where it is used to compute connected components, detect cycles, and rank nodes by centrality. In compiler design, traversal algorithms walk abstract syntax trees to perform type checking and code generation. The distinction between traversal and search is analogous to the distinction between mapping and navigation: one constructs a representation, the other uses it to reach a destination. A system that cannot traverse cannot search; traversal is the epistemic precondition of informed action.