Graphs/Traversal
From charlesreid1
Contents
Notes
Definition
Graph traversal is a systematic method for walking through every vertex and edge in the graph. Generally, a traversal visits each vertex exactly once. However, with an Euler tour (traversal), each edge is visited exactly once.
There are some similarities with tree traversal, but graph traversal is basically a more general version of tree traversal - trees are DAGs (directed acyclic graphs), so tree traversals are traversals on a DAG.
Recursion is an important concept in both graph and tree traversal - specifically for depth-first traversal methods.
Traversal is a useful building block for other algorithms. Traversal helps address questions of reachability - whether and how you can reach one vertex from another, finding the shortest path, finding whether a graph is connected, finding cycles, and finding spanning trees.
These algorithms all build on the idea of graph traversal, so this is a really important concept to nail down before moving on to other graph algorithms!
Depth first search and traversal generally uses recursion and backtracking to traverse all vertices on the graph.
Breadth first search and traversal generally uses a queue data structure to traverse all vertices on a graph. As each vertex is visited, neighbors of said vertex are added to the queue. Once a particular vertex is visited, the next vertex to visit is obtained by popping an item from queue.
Related
Recursion:
- See Recursion
Graphs:
- Graphs#Graph Traversals
- Graphs/Depth First Traversal
- Graphs/Breadth First Traversal
- Graphs/Euler Tour
- Graphs/Euler Circuit
Traversals on trees:
Breadth-first search and traversal on trees:
Depth-first search and traversal on trees:
OOP design patterns:
Flags
