Finding a Path
Problem: is there a path from vertex v to vertex w ?
As a function: bool isPath(Vertex v, Vertex w)
Approach to solving problem:
- examine vertices adjacent to v
- if any of them is w, then done
- otherwise try vertices two edges from v
- repeat, looking further and further from v
Two different approaches to order of searching:
- breadth-first search (BFS), depth-first search (DFS)
|