Graph Traversal
A common class of graph algorithms involves
- walking along edges and visiting vertices
- recording e.g. path taken, vertices visited, etc.
We often talk about graph search rather than graph traversal
Two strategies for graph traversal/search: depth-first, breadth-first
- DFS follows one path to completion before considering others
- DFS uses recursion or a stack, and backtracking
- BFS "fans-out" from the starting vertex ("spreading" subgraph)
- BFS maintains a queue of to-be-visited vertices
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}