graphs are not very useful if we just use them for storage — we also want to be able to search / traverse them to gather information
(abstract) questions we might want to ask:
- can we remove an edge and keep the graph connected?
- is a vertex reachable starting from somewhere else?
- what is the quickest way to get from one node to another?
- is there a tree that links all vertices?
graph traversal
three main uses for traversal:
- traverse for item search — can I reach
y
from x
?
- traverse for path finding — what is the part from
x
to y
?
- traverse fully — moving through the whole graph
two primary methods used to traverse a graph:
- depth-first search — go to deepest node first, when unwind (iterative / recursive solutions)
- breadth-first search — visit all neighbours, then their neighbours, etc. (iterative solutions)
both approaches will not traverse through some edges because they will not visit previously-visited vertices (to prevent cycles)