Depth First Search (DFS)

In this tutorial, you will learn the depth first search (DFS) algorithm for traversing a graph data structure with examples.

Depth-first search or depth-first traversal is a recursive algorithm used to visit all the vertices in a graph.

Depth First Search Algorithm

In the DFS algorithm, the traversal starts from a node and then follows its outgoing nodes. The search goes deeper and deeper until the goal node is found, or until a node that has no children is found.

DFS implementation puts each vertex in the graph into the following lists:

  • Visited.
  • Not Visited (Stack).

This marking is used to avoid cycles while traversing. The DFS algorithm performs the following operations:

  1. Start from any vertex. PUSH it onto the stack.
  2. POP the top item from the stack and add to the list of visisted nodes.
  3. Select a adjacent vertex that is not visisted and PUSH it onto the stack.
  4. Repeat steps 2 and 3 until stack is empty.

The formal algorithm is as follows:

1: SET STATUS=1 (Not Visted) for each node in G
2: Push the starting node A on the stack and set its STATUS=2 (waiting state)
3: Repeat Steps 4 and 5 until STACK is empty
4: Pop the top node N. Process it and set its STATUS=3 (Visited)
5: Push on the stack all the neighbours of N that are not visisted (whose STATUS=1) and set their STATUS=2 (waiting state)
6: EXIT

Depth First Search Algorithm Example

Consider the following graph with 5 vertices.

depth first search 1

We start from vertex A. PUSH A onto the visited list and PUSH all its adjacent nodes(D, C, B) onto the stack.

depth first search 2

Now POP D from the stack and visit it. Now visit the unvisited adjacent node(C) of D.

depth first search 3

PUSH unvisited adjacent node C of vertex D onto the stack and visit it.

depth first search 4

PUSH unvisited adjacent node E of vertex C onto the stack and visit it.

depth first search 5

Finally, POP B from the stack and visit it.

depth first search 6

Applications of Depth First Search Algorithm

  • To Find a path between two specified nodes, u and v, in an unweighted or weighted graph.
  • To determin whether a graph is connected or not.
  • To calculate the spanning tree of a connected graph.
Advertisements
Advertisements
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments