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.

__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)

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Graphs : Depth First Traversal |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.