Depth First Search

DFS(G)

1. for each vertex u∈V[G]

2. do color[u]=white
3. [u]=nil
4. time=0

5. for each certex u∈V[G]

6. do if color[u]=white
7. then DFS-Visit(u)

DFS-Visit(u)

1. color[u]=gray
2. time=time+1
3. discover[u]=time

4. for each v∈Adj[u] //explore edges

5. do if color[v]=white
6. then [v]=u
7. DFS-Visit(v)
8. color[u]=black
9. time++
10. finish[u]=time
    • These could be easily combined into an algorithm that uses a stack.

Properties

• DFS may result in different trees based on the order in which adjacent verticies are visited, but this will not change the effectiveness of the results.

• Running Time (V+E)

• The Predecessor subgraph forms a depth-first forest composed of several depth-first trees.

Theorems and Definitions

Theorem The start and finish times of each vertex visited expresses a correctly formed parenthesis structure. That is if (v...(u, then u)...v) where left parenthesis denotes discovery time and right parenthesis denotes finish time.

Definition We can classify edges based on the DFS forest G_{}

1. Tree edges are edges in the depth-first forest G_{}. Edge (u,v)∈Tree-Edge if v was first discovered while exploring (u,v)

2. Back edges are those edges (u,v) connecting vertex u to an ancestor v. Self loops are considered back edges.
3. Forward Edges are those nontree edges (u,v) connecting a vertex u to a descendent v.
4. Cross edges are all other edges. They can go between vertices in the same DFT as long as one vertex is not an ancestor of the other, or they can go between vertices in two different DFTs in the same forest.

We can always redraw a graph such that all forward and tree edges go down and all back edges go up.

Theorem (Theorem DAG No Back Edges) A directed graph is acyclic iff a depth-first search yields no "back" edges.

Applications

• TopologicallySortingDag

• StronglyConnectedComponents