4 Nov 2013

DFS(recursive) in Undirected Graph

Problem Statement:
         Implement recursive DFS traversal in 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.


Full Source Code : Link 


  
  /**
  * Procedure for Recursive DFS
  */
 public void dfs(){
  
  System.out.println("Recursive DFS :");
  Set<Map.Entry<Integer, Boolean>> entrys = vistedStatus.entrySet();
  
  Iterator<Entry<Integer, Boolean>> it = entrys.iterator();
  
  while(it.hasNext())
  {
   Map.Entry<Integer, Boolean> entry = it.next();
   boolean isVisited=entry.getValue();
   if(!isVisited){
    dfsUtil(entry.getKey()); 
   }
  }
 }

 public void dfsUtil(int vertex){
  List <Integer> list = adjList.get(vertex) ;

  vistedStatus.put(vertex, true) ;
  System.out.println(vertex + "\t");
  int size = list.size();
  for(int i = 0;i < size ; i++){
   int v=list.get(i);
   
   if(!vistedStatus.get(v))
    dfsUtil(v);
  }
 }

Please comment and post suggestions.

Happy Coding !! :)

No comments:

Post a Comment