Graph Search
Motivation: Given a graph
- check if network is connected (get from $A$ to $B$)
- find best driving directions (shortest path)
- etc etc
Search:
- find everything findable from a given vertex $s$
- don’t explore anything twice
- goal: $O(n+m)$
Algorithm
GenericAlgorithm(graph $G$, starting vertex $s$):
- initially only $s$ is explored
- while possible
- choose an edge $(u, v)$ with $u$ explored and $v$ unexplored
- mark $v$ explored
- if at the end $v$ is explored, there is a path from $s$ to $v$