[prev] [index] [next]

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)