Depth First Traversal

DEPTH FIRST TRAVERSAL:

Depth First works by selecting one vertex V of G as a start vertex, V is marked visited. Then each unvisited vertex adjacent to V is searched in turn using depth first search recursively. This process continues until a deadend i.e., a vertex with no adjacent unvisited vertices is encountered. At the deadend the algorithm backup one edge to the vertex it came from and tries to continue visiting unvisited vertices from there.

The algorithm halts after backing up to the starting vertex, with the latter being a deadend. By then, all the vertices in the same connected component as the starting vertex have been visited. If unvisited vertices still remain, the depth first search must be restarted at any one of them.

The two important key points of depth first search are:

^Ø   If path exists from one node to another node walk across the edge – exploring the edge.

^Ø   If path does not exist from one specific node to any other node, return to the previous

node where we have been before – backtracking.

The theme of depth first search is to explore if possible, otherwise backtrack.

To implement the DFS perform the following steps

1.     Choose any node in the graph. Designate it as the search node and mark it as visited.

2.     Using the adjacency matrix of the graph, find a node adjacent to the search node that has not been visited yet. Designate this as the new search node and mark it as visited.

3.     Repeat step2 using the new search node. If no nodes satisfying (2) can be found, return to the previous search node and continue from there.

4.     When return to the previous search node in (3) is impossible, the search from the originally chosen search node is complete.

5.     If the graph still contains unvisited nodes, choose any node that has not been visited and repeat step 1 through step 4.

Routine for Depth First Search

void DFS (Vertex V)

{

visited [V] = True;

for each W adjacent to V if(!visited[W])

DFS(W);

}

Depth First Search Vs Breadth First Search

Depth First Search

Back tracking is possible from a dead end.

Vertices    from    which    exploration is incomplete are processed in a LIFO order.

Search is done in one particular direction.

Breadth First search

Backtracking is not possible.

The vertices to be explored are organized as a FIFO order.

The vertices in the same level are maintained parallelly. (left to right)