DFS Iterative in Undirected Graph

Problem Statement: 
        Implement DFS traversal in a undirected Graph using stack:

Fig : Undirected Graph

Solution: 

DFS : Depth First Search

 DFS traversal starts from a node , explores as far as possibles and then backtracks. This algorithms explores the depth of a node and then backtracks along the same path.

Here we have implement DFS through a Stack.

Algorithm: 
        procedure DFS(Graph,source):
              create a stack S
              push source onto S
              mark source
              while S is not empty:
                  pop an item from S into v
                  for each edge e incident on v in Graph:
                      let w be the other end of e
                      if w is not marked:
                         mark w
                         push w onto S

Full Source Code: Link

       /**
  * Procedure for Iterative DFS using Stack
  */
 public void dfsIterative(int startNode) {
  System.out.println("Iterative DFS : ");
  Stack<Integer> stack = new Stack<Integer>();

  stack.push(startNode);
  vistedStatus.put(startNode, true);

  while (!stack.empty()) {

   int item = stack.pop();

   System.out.println("Poped Item : " + item);

   List<Integer> list = adjList.get(item);
   int size = list.size();

   for (int j = 0; j < size; j++) {
    int dest = list.get(j);

    if (!vistedStatus.get(dest)) {
     vistedStatus.put(dest, true);
     stack.push(dest);
    }
   }
  }
 }