Graph Traversal

Graph traversal systematically visits the vertices and edges of a graph; breadth-first search explores level by level while depth-first search explores as deeply as possible before backtracking, and together they underpin most graph algorithms.

Definition

Graph traversal is the process of visiting every vertex (and examining every edge) of a graph in a systematic order; breadth-first search visits vertices in order of distance from a source, and depth-first search follows each path to its end before backtracking.

Scope

This topic covers the two fundamental graph-search strategies, breadth-first search (BFS) and depth-first search (DFS), their queue- and stack-based implementations, and the structural information they reveal — reachability, connected components, shortest paths in unweighted graphs, topological ordering, cycle detection, and strongly connected components. It excludes weighted shortest paths and flow problems, which build on traversal but are treated separately.

Core questions

• How do BFS and DFS differ in the order they visit vertices, and what does each reveal?
• How does BFS compute shortest paths in an unweighted graph?
• How does DFS enable topological sorting, cycle detection and component decomposition?
• Why do both traversals run in time linear in the number of vertices plus edges?
• How are visited markers and frontier structures used to avoid revisiting vertices?

Key concepts

• breadth-first search (BFS)
• depth-first search (DFS)
• visited set
• queue and stack frontiers
• connected components
• topological sort
• cycle detection
• strongly connected components

Key theories

Breadth-first search and unweighted shortest paths

BFS visits vertices in nondecreasing order of distance from the source using a queue, so it computes the minimum number of edges from the source to every reachable vertex in linear time.

Depth-first search and linear graph algorithms

DFS, with its discovery and finishing times and edge classification, yields linear-time algorithms for topological sorting, cycle detection, and finding strongly connected components, as systematized by Tarjan.

Clinical relevance

Traversal algorithms are everywhere: BFS finds shortest hop counts in unweighted networks and underlies web crawlers and peer-to-peer broadcast; DFS drives dependency resolution and build systems via topological sort, deadlock detection, maze and puzzle solving, and component analysis in social and biological networks.

History

Breadth-first search dates to Moore's 1959 work on maze routing and related independent efforts. Depth-first search was placed on rigorous algorithmic footing by Robert Tarjan in 1972, whose linear-time algorithms for strongly connected components and biconnectivity demonstrated DFS as a powerful general tool.

Key figures

• Robert Tarjan
• Edward F. Moore
• John Hopcroft

Seminal works

• tarjan1972
• cormen2009

Frequently asked questions

When should I use BFS rather than DFS?

Use BFS when you need the shortest path in terms of number of edges or want to explore the graph in order of distance from a source. Use DFS for problems about structure — topological ordering, cycle detection, connected or strongly connected components — where exploring deeply and backtracking is natural.

Why are BFS and DFS both linear time?

Each vertex is marked visited and processed once, and each edge is examined a constant number of times, so the total work is proportional to the number of vertices plus the number of edges, written O(V + E).