EXPERT ANSWER
1. DFS or Depth First Search follows depth wise travesal in which the next vertex is remebered using the stack.
Rules for DFS are:
1. Unvisited adjacent vertex are visited and pushed in to the stack.
2. If there is no adjacent vertex found, it will popup from the stack and search till adjacent unvisited vertex found.
3. The rules 1 and 2 repeated till the stack become empty.
Initially the DFS start from the root node , that is vertext 1, Here there is an empty stack to the store the visited vertex
The neighouring nodes of 1 are , 2, 7 and 8.
As three of them are not visited , node 1 can visit any of the nodes 2,7 and 8. Here taken node 2 for numberwise traversal.
Node 2 then look for the unvisited node, which can take 3 or 6. Here taken unvisted node 3 and moved to the stack.
node 3 then look for the neighouring unvisited node and can take 4 or 5. Here taken vertex 4 and added to the stack
Vertex 4 then look for neighouring unvisited node and find none. So 4 is popped from the stack.
Next the control move on to the vertex 3 and look for the unvisited vertex, finds the node 5. The node 5 is then moved on to the stack.
5 then look for the unvisited node and find none. Hence the elemnt 5 is popped away from the stack.
The searching then mve on to vertex 3 and then look for the uvivties neighours, and find null. Hnce the vertex 3 is also popped from the stack.
Searching then move back on to the node 2, and searches for unvisited node and find the node 6 unvisited from 2 . Now 6 is visited and pushed to stack.
Next node 6 check for the neighouring node and finds none so popped up from the stack.
Now the node 2 look for unvisited neighours and find nill, node 2 is popped from the stack and the search move on to the node 1
