Graphs/Traversal

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

On a graph:

• Graphs/Breadth First Traversal
• Graphs/Depth First Traversal
• Graphs/Euler Tour

Tree traversal:

• Trees/Preorder
• Trees/Postorder
• Trees/Inorder

Breadth-first search and traversal on trees:

• BFS - breadth first search
• BFT - breadth first traversal

Depth-first search and traversal on trees:

• DFS - depth first search
• DFT - depth first traversal