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:

- Start from any vertex. PUSH it onto the stack.
- POP the top item from the stack and add to the list of visisted nodes.
- Select a adjacent vertex that is not visisted and PUSH it onto the stack.
- 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.

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

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

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

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

Finally, POP B from the stack and visit it.

#### 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.