[prev] 54 [next]

Finding a Path

Questions on paths:
  • is there a path between two given vertices (src,dest)?
  • what is the sequence of vertices from src to dest?
Approach to solving problem:
  • examine vertices adjacent to src
  • if any of them is dest, then done
  • otherwise try vertices two edges from src
  • repeat looking further and further from src
Two strategies for graph traversal/search:   depth-first,   breadth-first
  • DFS follows one path to completion before considering others
  • BFS "fans-out" from the starting vertex ("spreading" subgraph)