DFS

DFS
Runtime	O(V + E)
Space	O(V)
Class	Graph Algorithms

Depth-first search is a graph traversal algorithm.

Approach

The basic idea of DFS is to visit every child of the visiting node before moving on to the next unvisited node.

1. Every node besides one start out being unvisited (white).
2. DFS begin by visiting a source node. Upon entering a node, DFS marks it as visiting (grey).
3. DFS then visits all of its child nodes.
4. After it has visited all children of a grey node, it marks the visiting parent node as visited (black).
5. This continues until every node is black.

Implementation

 DFS_visit(u) {
     time = time + 1
     d[u] = time
     color[u] = 'grey'
     for each v in adj[u] {
         if color[u] == white
             DFS_visit(u)
     }
     f[u] = time++
     color[u] = black
 }

Variations and Applications

Edge classification and cycle detection

DFS can classify edges based on the color of the node it is visiting.

• If the node is white (unvisited), the edge is called a tree edge. After DFS ends, all the tree edges form a spanning tree stemming from the source node (if the graph is connected).
• If the node is grey (visiting), the edge is called a back edge. During a visit, any grey node is a predecessor of the current node, therefore edges to grey node goes "back" up. Notably, the presence of back edges indicate that there is a cycle.
• If the node is black (visited), the edge is called a cross edge. They "cross" from one branch to another, neither being in the tree nor creating a cycle. I've not really seen any uses for this yet.

Entry time and exit time

An addition to DFS keeps track of the entry time and exit time of nodes: that is, it keeps an ordering of when nodes are marked as grey/black. An index is used to keep track of this, incrementing every time a node's color change.

This is useful primarily for topological sort. A strategy for this problem involves DFS-ing the graph and sorting the nodes by exit times.