A graph is traversed in a depthward motion by using a stack to go to the next vertex, by an algorithm known as Depth First Search (DFS) algorithm.
DFS algorithm traverses from A to B to C to D first then to E, then to F and lastly to G.
The following are the rules employed by the DFS algorithm:
The following are the steps:
Step 1 - Initialize the stack.
Step 2 - Mark S as visited and put it onto the stack. Any unvisited adjacent node is explored from S. Out of the three nodes, pick any one, preferable take in alphabetical order.
Step 3 - Mark A as visited and put it onto the stack. Any unvisited adjacent node from A are explored. Both S and D are adjacent to A but the concern is about the unvisited nodes only.
Step 4 - Visit D and mark it as visited and put onto the stack. Here, both B and C nodes are there, which are adjacent to D and both are unvisited. However, choose in an alphabetical order.
Step 5 - Choose B, mark it as visited and put onto the stack. Here B does not have any unvisited adjacent node. So, pop B from the stack.
Step 6 - Check the stack top for return to the previous node and check if it has any unvisited nodes. Here, D is found to be on the top of the stack.
Step 7 - Only unvisited adjacent node is from D is C now. So visit C, mark it as visited and put it onto the stack.
As C does not have any unvisited adjacent node so the stack is kept popping until a node with an unvisited adjacent node is found. Here, it is none and hence keep popping until stack is empty.
Data Structure & Algorithms Related Interview Questions
|RDBMS Interview Questions||DBMS Interview Questions|
|Adv Java Interview Questions||Core Java Interview Questions|
|C Interview Questions||Database Administration Interview Questions|
|CSS Advanced Interview Questions||Maven Interview Questions|
|Computer architecture Interview Questions||Object Oriented Analysis and Design Interview Questions|
|Standard Template Library (STL) Interview Questions||Xml Publisher Interview Questions|
All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd
Wisdomjobs.com is one of the best job search sites in India.