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.