Depth first search notes.

Depth first search is done on tree, tree structure or graph. It starts by selecting a node as a root of a graph and explores one branch before backtracking.

In this process it creates a depth first search tree. The edges in this depth first search tree are classified into three categories.

FORWARD EDGES:

These edges point from parent node to its descendents.

BACK EDGES:

These edges point from descendants to ancestors.

CROSS EDGES:

All the edges that doesn't fit in above two categories fits here.

To start the depth first search any node can be chosen as a root whereas in directed graph we dont have that luxury. I we need to randomly pick a vertex as a root and then further the depth first search. If it happens that all the vertices are not visited with this approach then pick another randomly and do the depth first search until all the vertices are visited. (I am not sure about the above implementation of DFS for directed graphs. It is just my own version of writing it).

Important applications of Depth first search include.

1) Finding connected components.

2) Topological sorting.

3) Finding strongly connected components.

4) Solving puzzles like mazes through backtracking.

5) Finding 2-(edge or vertex)-connected components.