4 Nov 2013

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);
    }
   }
  }
 }

2 comments:

  1. Very good blog you have here but I was wondering if you
    knew of any forums that cover thhe samje topics discussed here?
    I'd really love to be a part oof group where I can get suggestions from other
    knowledgeable individuals that share the sae interest.
    If you have any recommendations, please lett me know.
    Appreciate it!

    my homepage xbox live code generator

    ReplyDelete
  2. Usually I don't learn article on blogs, however
    I would like to say that this write-up very pressured me to try and do it!

    Your writing style has been surprised me. Thank
    you, quite nice post.

    Also visit my web site ... Summoners War Sky Arena Hack

    ReplyDelete