DFS (depth first search) in Data Structure


Depth First Search DFS is also an algorithm for traversing and searching graph data structures like BFS. Nodes in BFS are visited deeply (in depth).
The stack is used to implement DFS in the ta structure. DFS is a recursive algorithm that works on the principle of backtracking.

DFS is used to analyze networks, map routes and solve other computer science problems. DFS Algorithm:- In DFS we first visit the initial node by stack. Then putting all its adjacent nodes in the stack, visiting the node at the top of the stack, putting all its adjacent nodes in the stack and repeating the process until the stack is empty. Let us understand its algorithm by the following example:
Step 1: - The stack is initialized. Step 2: - Marks node A visited and puts it in the stack. Node A has three adjacent nodes B, C, and D. We can choose any of these nodes. We will choose in alphabetical order. Step 3: - Will mark node B visited and put it in the stack. Now, we will select any unvisited adjacent nodes of B. The adjacent nodes of B are A and E. Since A has already visited, we will select E. Step 4: - will visit E and mark it visited and put it in the stack. Here, two adjacent nodes C and D of node E are both unvisited, so we will select C.
Step 5: - We will visit c and mark it visited and put it in the stack. There is no unvisited adjacent node of B here, so we will remove it from the stack. Step 6: - Now E is back at the top of the stack, now we will see if it has any unvisited adjacent node. Its adjacent unvisited node is D.
By Engineers Baba
Step 7: - Now we will visit node D and mark it visited and put it in the stack.
Now there is no node left to visit, now we will take all the nodes out of the stack and when the stack is empty then the program will end. Request- If you like this post, then tell us through the comment and share it with your friends.









Post a Comment

0 Comments