Topics
- tricolor algorithm
- breadth-first search
- depth-first search
- cycle detection
- topological sort
- connected components
Abstractly, graph traversal algorithms can be expressed in terms of the tricolor algorithm. In the tricolor algorithm each node of the graph is assigned a color that changes over time:
- White nodes are undiscovered nodes that have not yet been seen in the current traversal and may even be unreachable.
- Black nodes are nodes that are reachable and that the algorithm is done with.
- Gray nodes are nodes that have been discovered but that the algorithm is not done with yet. They are at the frontier between the white ad black nodes.
A typical graph traversal algorithm starts with no black nodes and the root is gray. As the algorithm proceeds, white nodes turn into gray nodes and gray nodes convert to black ones. Eventually there are no gray nodes left and the algorithm is done. The tricolor algorithm maintains a key invariant at all times: there are no edges from white nodes to black nodes. This is clearly true at the beginning (root is gray,all others are white) and it is also true at the end because we know that any remaining white nodes cannot be reached from the black nodes (a node turns black only when it has been fully explored).
The Algorithm
- Initially color all nodes white (unexplored)
- Color the root gray.
- while some gray node x exist
- color some white successors of x gray
- if x has no successors left, color it black
This algorithm is abstract. It is up to the implementation of a particular specialized traversal algorithm to :
- Decide which gray node(s) x to start with
- Decide which neighbors of a gray node to color gray
- Delay coloring a node black.
One key advantage in defining graph search/traversal in terms of the tricolor algorithm is that the tricolor algorithm works even when gray nodes are worked on concurrently, as long as the black-white invariant is maintained.