A path is a sequence of connected edges that lets you travel through a graph from one vertex to another. Each edge must begin where the previous edge ends. section 13.5
Following a graph path
In the animal follower graph, Giraffe→Crocodile→Monkey→Giraffe forms a path whose first and last vertices match, so it is also a cycle. A path that does not return to its starting vertex is not a cycle. section 13.5
Paths help describe structure in several common data structures:
- Trees contain simple paths from the root to leaves; no node appears twice, and each node has one parent except the root. section 11.2
- A node is an ancestor of another when it lies on the path between the root and that node; the reverse relationship is descent. section 11.2
- A tree's height is the length of its longest root-to-leaf path, while a heap has height as small as log(n). section 11.2 section 10.11
- A graph with no cycles is acyclic; a cycle is a path that starts and ends at the same vertex. section 13.5
Use the graph figure to trace connected edges, identify cycles, and distinguish paths that return to their starting vertex. section 13.5
