Paths and Walks
What You'll Learn
You'll learn the precise difference between a path and a walk in graph theory, and why this distinction matters when navigating graphs.
The Core Idea
When moving through a graph from one vertex to another via edges, we use specific terminology to describe these journeys.
A walk is any sequence of vertices where each consecutive pair is connected by an edge. You can visit the same vertex multiple times, and you can traverse the same edge more than once. Think of it like walking through a city — you're allowed to circle back through the same intersection or use the same street twice.
A path, however, is more restrictive: it's a walk where no vertex is repeated. Once you visit a vertex, you can't return to it in that path. This is like taking a tour where you visit each landmark exactly once without backtracking.
Why It Matters
In an undirected graph with vertices A, B, and C connected in a line (A—B—C):
- A → B → C is both a walk and a path (no repetition)
- A → B → A → B → C is a walk but not a path (vertex A and B are repeated)
The concept of a path is crucial for finding the shortest route between two points, detecting cycles, and many graph algorithms you'll encounter. Walks are more general and useful when repetition is acceptable or even desired.
Key Takeaway: A path is a sequence of distinct vertices connected by edges (no repeats), while a walk allows revisiting vertices and edges — all paths are walks, but not all walks are paths.