Test yourself
Consider the following graph..
Which of the following is a valid order node visiting order generated using dfs ? (beginning from A)
Which node will be the last to be popped out of the stack ?
The depth first search algorithm is used for traversing all the nodes of a given graph.
1) Initialize an empty stack and pick any node of the graph to be the starting node.
2) Insert the selected node into the stack.
3) Next visit any unvisited adjacent vertex of the current node.
4) If no such adjacent unvisited vertex exists, then pop the vertex from the stack, and move on to the next vertex on the top of the stack.
5) Continue repeating steps 2-5 until every node has been pushed and popped out of the stack, ie. every vertex has been visited.