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)