Implement DepthFirst search with stackSolutionSolution Imple

Implement Depth-First search with stack

Solution

Solution:

Implementation of Depth First Search Using a Stack:
algorithms uses a stack S of vertices. A vertex can be pushed onto the stack more than once, in act, the same vertex could be on the stack in several places simultaneously. Being pushed onto the stack does not necessarily imply visitation; we must indicate the visitation of v by explicitly writing visited [v] := true, and that assignment may not occur more than once. Here is a stack algorithm for depth first search, which we call DFS-A(G, s).
DFS-A(G,s)
for all v in V[G] do
visited[v] := false
end for
S := EmptyStack
Push(S,s)
while not Empty(S) do
u := Pop(S)
if not visited[u] then
visted[u] := true
for all w in Adj[u] do
if not visited[w] then
Push(S,w)
end if
end for
end if
end while

DFS-A can have multiple copies on the stack at the same time. However, the total number of iterations of the innermost loop of DFS-A cannot exceed the number of edges of
G, and thus the size of S cannot exceed m. The running time of DFS-A is O(n+m).
DFS.java
Class Main {
  
   public void dfs() {
       // DFS uses Stack data structure
       Stack stack = new Stack();
       stack.push(this.rootNode);
       rootNode.visited=true;
       printNode(rootNode);
       while(!stack.isEmpty()) {
           Node node = (Node)s.peek();
           Node child = getUnvisitedChildNode(n);
           if(child != null) {
               child.visited = true;
               printNode(child);
               s.push(child);
           }
           else {
               s.pop();
           }
       }
       // Clear visited property of nodes
       clearNodes();
   }
}

Class Node {
Char data;
Public Node(char c) {
this.data=c;
}
}