Path
- Identify a path from a source vertex to a destination vertex.
A path is a sequence of consecutive edges in a graph.
Alternatively, we can define "path" as a sequence of vertices where each vertex in the sequence is adjacent to the vertex next to it.
Consider the following graph:
Here are two pathes from $A$ to $C$: $(A, C)$ and $(A, B, D, C)$.
A simple path is a path that does not repeat any nodes or edges.
In this class, when I say "path," I mean "simple path."
Aside: In some references, what I defined as "path" is described as "walk," and instead "simple path" is called, simply, "path."
Exercise List the edges on a directed path from $B$ to $E$ and from $C$ to $E$.
Solution
- Directed path from $B$ to $E$: $((B, D), (D, E))$.
- There is no directed path from $C$ to $E$.