Graph Traversals

One of the most fundamental graph problem is: traverse all its nodes and edges systematically. For example, mazes are naturally represented as graphs, and therefore finding a path in a maze can easily be solved by executing some graph traversal algorithm.

The key idea behind graph traversals is: MARK every vertex when we FIRST visit it, and keep track of those vertices NOT YET EXPLORED. In such an approach, each vertex in the graph will be in one of three possible states:

1. UNDISCOVERED
2. DISCOVERED
3. PROCESSED

and in a given traversal, the state progression of a vertex would be UNDISCOVERED, then DISCOVERED, and finally PROCESSED.

Thus, at the core of a graph traversal implementation is a data structure to keep track of the work to be done, that is, the vertices that have been discovered but have not been processed yet. During a traversal, when we reach an UNDISCOVERED vertex, we mark it as DISCOVERED and add it to the data structure as "work to be done". If we reach a vertex that is already DISCOVERED/PROCESSED, we ignore it.

If the graph being traversed is DIRECTED, then edge will be traversed once; if the graph is UNDIRECTED, then each edge will be traversed twice.

Two of the most often used graph traversal algorithms are:

• Breadth First Search
• Depth First Search

In a following post we will describe each of these approaches. Stay tuned.