Depth-First Search or DFS algorithm is a recursive algorithm that uses the backtracking principle. It entails conducting exhaustive searches of all nodes by moving forward if possible and backtracking, if necessary. To visit the next node, pop the top node from the stack and push all of its nearby nodes into a stack. Topological sorting, scheduling problems, graph cycle detection, and solving puzzles with just one solution, such as a maze or a sudoku puzzle, all employ depth-first search algorithms. Other applications include network analysis, such as determining if a graph is bipartite.
What is a Graph Traversal Algorithm?
Graph traversal is a search technique for finding a vertex in a graph. In the search process, graph traversal is also used to determine the order in which it visits the vertices. Without producing loops, a graph traversal finds the edges to be employed in the search process.
There are two methods to traverse a graph data structure:
- Depth-First Search or DFS algorithm
- Breadth-First Search or BFS algorithm
Following your understanding of graph traversal, you will learn about the depth-first search algorithm.
What is a Depth-First Search Algorithm?
The depth-first search or DFS algorithm traverses or explores data structures, such as trees and graphs. The algorithm starts at the root node (in the case of a graph, you can use any random node as the root node) and examines each branch as far as possible before backtracking.
When a dead-end occurs in any iteration, the Depth First Search (DFS) method traverses a network in a deathward motion and uses a stack data structure to remember to acquire the next vertex to start a search.
Following the definition of the dfs algorithm, you will look at an example of a depth-first search method for a better understanding.
Example of Depth-First Search Algorithm
The outcome of a DFS traversal of a graph is a spanning tree. A spanning tree is a graph that is devoid of loops. To implement DFS traversal, you need to utilize a stack data structure with a maximum size equal to the total number of vertices in the graph.
To implement DFS traversal, you need to take the following stages.
Step 1: Create a stack with the total number of vertices in the graph as the size.
Step 2: Choose any vertex as the traversal's beginning point. Push a visit to that vertex and add it to the stack.
Step 3 - Push any non-visited adjacent vertices of a vertex at the top of the stack to the top of the stack.
Step 4 - Repeat steps 3 and 4 until there are no more vertices to visit from the vertex at the top of the stack.
Step 5 - If there are no new vertices to visit, go back and pop one from the stack using backtracking.
Step 6 - Continue using steps 3, 4, and 5 until the stack is empty.
Step 7 - When the stack is entirely unoccupied, create the final spanning tree by deleting the graph's unused edges.
Consider the following graph as an example of how to use the dfs algorithm.
Step 1: Mark vertex A as a visited source node by selecting it as a source node.
- You should push vertex A to the top of the stack.
Step 2: Any nearby unvisited vertex of vertex A, say B, should be visited.
- You should push vertex B to the top of the stack.
Step 3: From vertex C and D, visit any adjacent unvisited vertices of vertex B. Imagine you have chosen vertex C, and you want to make C a visited vertex.
- Vertex C is pushed to the top of the stack.
Step 4: You can visit any nearby unvisited vertices of vertex C, you need to select vertex D and designate it as a visited vertex.
- Vertex D is pushed to the top of the stack.
Step 5: Vertex E is the lone unvisited adjacent vertex of vertex D, thus marking it as visited.
- Vertex E should be pushed to the top of the stack.
Step 6: Vertex E's nearby vertices, namely vertex C and D have been visited, pop vertex E from the stack.
Step 7: Now that all of vertex D's nearby vertices, namely vertex B and C, have been visited, pop vertex D from the stack.
Step 8: Similarly, vertex C's adjacent vertices have already been visited; therefore, pop it from the stack.
Step 9: There is no more unvisited adjacent vertex of b, thus pop it from the stack.
Step 10: All of the nearby vertices of Vertex A, B, and C, have already been visited, so pop vertex A from the stack as well.
Now, examine the pseudocode for the depth-first search algorithm in this.
Pseudocode of Depth-First Search Algorithm
Pseudocode of recursive depth-First search algorithm.
|
Depth_First_Search(matrix[ ][ ] ,source_node, visited, value) { If ( sourcce_node == value) return true // we found the value visited[source_node] = True for node in matrix[source_node]: If visited [ node ] == false Depth_first_search ( matrix, node, visited) end if end for return false //If it gets to this point, it means that all nodes have been explored. //And we haven't located the value yet. } |
Pseudocode of iterative depth-first search algorithm
|
Depth_first_Search( G, a, value): // G is graph, s is source node) stack1 = new Stack( ) stack1.push( a ) //source node a pushed to stack Mark a as visited while(stack 1 is not empty): //Remove a node from the stack and begin visiting its children. B = stack.pop( ) If ( b == value) Return true // we found the value Push all the uninvited adjacent nodes of node b to the Stack For all adjacent node c of node b in graph G; //unvisited adjacent If c is not visited : stack.push(c) Mark c as visited Return false // If it gets to this point, it means that all nodes have been explored. //And we haven't located the value yet. |
Next, in the dfs tutorial, you will explore the complexity of the depth-first search algorithm.
Complexity Of Depth-First Search Algorithm
The time complexity of depth-first search algorithm
If the entire graph is traversed, the temporal complexity of DFS is O(V), where V is the number of vertices.
- If the graph data structure is represented as an adjacency list, the following rules apply:
- Each vertex keeps track of all of its neighboring edges. Let's pretend there are V vertices and E edges in the graph.
- You find all of a node's neighbors by traversing its adjacency list only once in linear time.
- The sum of the sizes of the adjacency lists of all vertices in a directed graph is E. In this example, the temporal complexity is O(V) + O(E) = O(V + E).
- Each edge in an undirected graph appears twice. Once at either end of the edge's adjacency list. This case's temporal complexity will be O(V) + O (2E) O(V + E).
- If the graph is represented as adjacency matrix V x V array:
- To find all of a vertex's outgoing edges, you will have to traverse a whole row of length V in the matrix.
- Each row in an adjacency matrix corresponds to a node in the graph; each row stores information about the edges that emerge from that vertex. As a result, DFS's temporal complexity in this scenario is O(V * V) = O. (V2).
The space complexity of depth-first search algorithm
Because you are keeping track of the last visited vertex in a stack, the stack could grow to the size of the graph's vertices in the worst-case scenario. As a result, the complexity of space is O. (V).
After going through the complexity of the dfs algorithm, you will now look at some of its applications.
Application Of Depth-First Search Algorithm
The minor spanning tree is produced by the DFS traversal of an unweighted graph.
- Detecting a graph's cycle: A graph has a cycle if and only if a back edge is visible during DFS. As a result, you may run DFS on the graph to look for rear edges.
- Topological Sorting: Topological Sorting is mainly used to schedule jobs based on the dependencies between them. In computer science, sorting arises in instruction scheduling, ordering formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbols dependencies linkers.
- To determine if a graph is bipartite: You can use either BFS or DFS to color a new vertex opposite its parents when you first discover it. And check that each other edge does not connect two vertices of the same color. A connected component's first vertex can be either red or black.
- Finding Strongly Connected Components in a Graph: A directed graph is strongly connected if each vertex in the graph has a path to every other vertex.
- Solving mazes and other puzzles with only one solution:By only including nodes the current path in the visited set, DFS is used to locate all keys to a maze.
- Path Finding: The DFS algorithm can be customized to discover a path between two specified vertices, a and b.
- Use s as the start vertex in DFS(G, s).
- Keep track of the path between the start vertex and the current vertex using a stack S.
- Return the path as the contents of the stack as soon as destination vertex c is encountered.
Finally, in this tutorial, you will look at the code implementation of the depth-first search algorithm.
Code Implementation Of Depth-First Search Algorithm
|
#include <stdio.h> #include <stdlib.h> #include <stdlib.h> int source_node,Vertex,Edge,time,visited[10],Graph[10][10]; void DepthFirstSearch(int i) { int j; visited[i]=1; printf(" %d->",i+1); for(j=0;j<Vertex;j++) { if(Graph[i][j]==1&&visited[j]==0) DepthFirstSearch(j); } } int main() { int i,j,v1,v2; printf("\t\t\tDepth_First_Search\n"); printf("Enter the number of edges:"); scanf("%d",&Edge); printf("Enter the number of vertices:"); scanf("%d",&Vertex); for(i=0;i<Vertex;i++) { for(j=0;j<Vertex;j++) Graph[i][j]=0; } for(i=0;i<Edge;i++) { printf("Enter the edges (V1 V2) : "); scanf("%d%d",&v1,&v2); Graph[v1-1][v2-1]=1; } for(i=0;i<Vertex;i++) { for(j=0;j<Vertex;j++) printf(" %d ",Graph[i][j]); printf("\n"); } printf("Enter the source: "); scanf("%d",&source_node); DepthFirstSearch(source_node-1); return 0; } |
Next Steps
You learned the depth-first search or dfs algorithm with examples, learned how to implement it in code, and saw various dfs algorithm applications in this tutorial.
If you're seeking a more extensive study that goes beyond Data Structure and covers the most in-demand programming languages and abilities today, Simplilearn's Post Graduate Program in Full Stack Web Development is for you.
Do you have any questions about this tutorial on the depth-first search algorithm? If you do, please leave them in the comments section at the bottom of this page. Our specialists will respond to your questions at the earliest!
