From Chapter 22, Elementary Graph Algorithms, section 22.3 (page 603)
DFS visits the nodes in a depth first fashion and creates a forest of depth-first trees. It colours the nodes white, grey or black; and classifies the edges into tree, back, forward and cross edges.
The nodes are coloured as follows:
- Every node starts as white
- When a node is discovered for the first time, it is coloured grey. Then all it’s descendants are explored in a depth-first fashion
- After all its descendants are explored, it is coloured black
The edges are classified as:
- Tree Edge: When an edge leads to a white node, it is a tree edge. This edge is a part of the Depth First Tree.
- Back Edge: When an edge leads to a grey node, it is a back edge. This implies a cycle. Self loops are also back edges.
- Forward Edge: When an edge leads to a black edge that is the descendant of the current node, then it is a forward edge
- Cross Edge: These are all the other edges. E.g. edges from one tree to another. These are those edges which lead to a black edge but that is not the descendant of the current node.
Grey Node is an ancestor
At any point in the process, a grey node is a ancestor of the current node along a path of tree edges
Topological Sort
Inserting nodes into a list when they are coloured black during the DFS process gives us the topological sort. The element inserted last is the element with no dependencies.
If a back edge is discovered during the DFS, then the graph contains a cycle and so topological sort is not possible.
Strongly Connected Components
DFS can be used to decompose a graph into its strongly connected components.
TODO.