Undirected Graph API

Problem Statement:
        Implement given below operations in a un-directed graph to form the basic API of graph.

Fig: Undirected Graph

Operations:

1. Adding Edge 
2. DFS iterative
3. DFS recursive
4. BFS
5. Get the List of the connected nodes to a given vertex

Solution : 

Full Source Code: Link

Note : For representation of graph, we will be maintain Adjacency list and not matrix in all the posts

1. Adding Edge : 

This operation demonstrates adding of an edge in a undirected Graph , the two ends of the edge are marked as un-visited and the edge is added in both ways from 'source' to 'destination ' and also from 'destination' to 'source' as the graph is undirected.
      

  /**
    * Edge in a un-directed graph
    */
 private void addEdge(int src, int dest) {

  /*Forward Edge */
  ArrayList<Integer> list=adjList.get(src);   
  if(list==null)
   list=new ArrayList<Integer>();

  list.add(dest);
  adjList.put(src,list); 
  vistedStatus.put(src, false);  //visit status set to false

  /* Reverse Edge */
  list=adjList.get(dest);   
  if(list==null)
   list=new ArrayList<Integer>();

  list.add(src);
  adjList.put(dest,list); 
  vistedStatus.put(dest, false);  //visit status set to false
 }
  

2.  DFS Iterative 


DFS stands for Depth First Search , this traversal starts from a node and explores as far as possible and backtracks. Below Iterative DFS has used a stack for implementation.

  _
       /**
  * 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);
      }
     }
    }
 }
  _

3. DFS Recursive :

Here is a recursive solution for DFS
 

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

4. BFS (Breadth First Search) :

The BFS begins at one point and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on.
Here is an BFS implementation using Queue.

  /** Desc: Breadth First Search: using queue to visit to all nodes in a connected graph  
  */
 public void bfs(int startNode)
 {
  Queue<Integer> bfsQueue = new LinkedList<Integer>();

  // stating node visit status set to true
  vistedStatus.put(startNode, true);

  // start node added to Queue
  bfsQueue.add(startNode);

  while(!bfsQueue.isEmpty())
  {
   // Node poped from Queue
   int node=bfsQueue.poll();
   System.out.println("Node poped is : "+node);

   // all connected node list of a give node
   List<Integer> list=adjList.get(node);

   int size=list.size();
   System.out.print("Connected Nodes are : ");
   for(int i=0;i <size; ++i)
   {
    int adjNode=list.get(i);
    System.out.print(adjNode +"   ");
    boolean isVisited=vistedStatus.get(adjNode);
    if(!isVisited)
    {
     vistedStatus.put(adjNode, true);
     bfsQueue.add(adjNode);
    }
   }
   System.out.println("\n===================");
  }
 }
  

5. Get the list of connected nodes to a given vertex:

This operation returns the list of nodes connected directly to a given node

       /**
  * Get the list of connected nodes to a given vertex
  * @param vertex : given vertex
  * @return List of vertices connected to given vertex
  */
 public List<Integer> adj(int vertex){
  return adjList.get(vertex);
 }
  

Please comment if you like the post and also if any suggestions



Happy Coding !! :)