DSA using Java - Graph

Overview

Graph is a datastructure to model the mathematical graphs. It consists of a set of connected pairs called edges of vertices. We can represent a graph using an array of vertices and a two dimentional array of edges.

Important terms

Vertex − Each node of the graph is represented as a vertex. In example given below, labeled circle represents vertices. So A to G are vertices. We can represent them using an array as shown in image below. Here A can be identified by index 0. B can be identified using index 1 and so on.

Edge − Edge represents a path between two vertices or a pne between two vertices. In example given below, pnes from A to B, B to C and so on represents edges. We can use a two dimentional array to represent array as shown in image below. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.

Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. In example given below, B is adjacent to A, C is adjacent to B and so on.

Path − Path represents a sequence of edges betweeen two vertices. In example given below, ABCD represents a path from A to D.

Basic Operations

Following are basic primary operations of a Graph which are following.

Add Vertex − add a vertex to a graph.

Add Edge − add an edge between two vertices of a graph.

Display Vertex − display a vertex of a graph.

Add Vertex Operation

//add vertex to the array of vertex
pubpc void addVertex(char label){
   lstVertices[vertexCount++] = new Vertex(label);
}

Add Edge Operation

//add edge to edge array
pubpc void addEdge(int start,int end){
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}

Display Edge Operation

//display the vertex
pubpc void displayVertex(int vertexIndex){
   System.out.print(lstVertices[vertexIndex].label+" ");
}   

Traversal Algorithms

Following are important traversal algorithms on a Graph.

Depth First Search − traverses a graph in depthwards motion.

Breadth First Search − traverses a graph in breadthwards motion.

Depth First Search Algorithm

Depth First Search algorithm(DFS) traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.

As in example given above, DFS algorithm traverses from A to B to C to D first then to E, then to F and lastly to G. It employs following rules.

Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Push it in a stack.

Rule 2 − If no adjacent vertex found, pop up a vertex from stack. (It will pop up all the vertices from the stack which do not have adjacent vertices.)

Rule 3 − Repeat Rule 1 and Rule 2 until stack is empty.

pubpc void depthFirstSearch(){
   //mark first node as visited
   lstVertices[0].visited = true;
   //display the vertex
   displayVertex(0);   
   //push vertex index in stack
   stack.push(0);

   while(!stack.isEmpty()){
      //get the unvisited vertex of vertex which is at top of the stack
      int unvisitedVertex = getAdjUnvisitedVertex(stack.peek());
      //no adjacent vertex found
      if(unvisitedVertex == -1){
         stack.pop();
      }else{
         lstVertices[unvisitedVertex].visited = true;
         displayVertex(unvisitedVertex);
         stack.push(unvisitedVertex);
      }
   }

   //stack is empty, search is complete, reset the visited flag        
   for(int i=0;i<vertexCount;i++){
      lstVertices[i].visited = false;
   }        
}

Breadth First Search Algorithm

Breadth First Search algorithm(BFS) traverses a graph in a breadthwards motion and uses a queue to remember to get the next vertex to start a search when a dead end occurs in any iteration.

As in example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs following rules.

Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Insert it in a queue.

Rule 2 − If no adjacent vertex found, remove the first vertex from queue.

Rule 3 − Repeat Rule 1 and Rule 2 until queue is empty.

pubpc void breadthFirstSearch(){
   //mark first node as visited
   lstVertices[0].visited = true;
   //display the vertex
   displayVertex(0);   
   //insert vertex index in queue
   queue.insert(0);

   int unvisitedVertex;
   while(!queue.isEmpty()){
      //get the unvisited vertex of vertex which is at front of the queue
      int tempVertex = queue.remove();            
      //no adjacent vertex found
      while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){    
         lstVertices[unvisitedVertex].visited = true;
         displayVertex(unvisitedVertex);
         queue.insert(unvisitedVertex);               
      }
   }   

   //queue is empty, search is complete, reset the visited flag        
   for(int i=0;i<vertexCount;i++){
      lstVertices[i].visited = false;
   }    
}

Graph Implementation

Stack.java

package com.tutorialspoint.datastructure;

pubpc class Stack {
   private int size;           // size of the stack
   private int[] intArray;     // stack storage
   private int top;            // top of the stack

   // Constructor 
   pubpc Stack(int size){
      this.size = size;           
      intArray = new int[size];   //initiapze array
      top = -1;                   //stack is initially empty
   }

   // Operation : Push
   // push item on the top of the stack 
   pubpc void push(int data) {

      if(!isFull()){
         // increment top by 1 and insert data 
         intArray[++top] = data;
      }else{
         System.out.println("Cannot add data. Stack is full.");
      }      
   }

   // Operation : Pop
   // pop item from the top of the stack 
   pubpc int pop() {
      //retrieve data and decrement the top by 1
      return intArray[top--];        
   }

   // Operation : Peek
   // view the data at top of the stack    
   pubpc int peek() {       
      //retrieve data from the top
      return intArray[top];
   }

   // Operation : isFull
   // return true if stack is full 
   pubpc boolean isFull(){
      return (top == size-1);
   }
   
   // Operation : isEmpty
   // return true if stack is empty 
   pubpc boolean isEmpty(){
      return (top == -1);
   }
}

Queue.java

package com.tutorialspoint.datastructure;

pubpc class Queue {
    
   private final int MAX;
   private int[] intArray;
   private int front;
   private int rear;
   private int itemCount;

   pubpc Queue(int size){
      MAX = size;
      intArray = new int[MAX];
      front = 0;
      rear = -1;
      itemCount = 0;
   }

   pubpc void insert(int data){
      if(!isFull()){
         if(rear == MAX-1){
            rear = -1;            
         }       

         intArray[++rear] = data;
         itemCount++;
      }
   }

   pubpc int remove(){
      int data = intArray[front++];
      if(front == MAX){
         front = 0;
      }
      itemCount--;
      return data;  
   }

   pubpc int peek(){
      return intArray[front];
   }

   pubpc boolean isEmpty(){
      return itemCount == 0;
   }

   pubpc boolean isFull(){
      return itemCount == MAX;
   }

   pubpc int size(){
      return itemCount;
   }    
}

Vertex.java

package com.tutorialspoint.datastructure;

pubpc class Vertex {
   pubpc char label;
   pubpc boolean visited;

   pubpc Vertex(char label){
      this.label = label;
      visited = false;
   }   
}

Graph.java

package com.tutorialspoint.datastructure;

pubpc class Graph {
   private final int MAX = 20;
   //array of vertices
   private Vertex lstVertices[];
   //adjacency matrix
   private int adjMatrix[][];
   //vertex count
   private int vertexCount;

   private Stack stack;
   private Queue queue;

   pubpc Graph(){
      lstVertices = new Vertex[MAX];
      adjMatrix = new int[MAX][MAX];
      vertexCount = 0;
      stack = new Stack(MAX);
      queue = new Queue(MAX);
      for(int j=0; j<MAX; j++) // set adjacency
         for(int k=0; k<MAX; k++) // matrix to 0
            adjMatrix[j][k] = 0;
   } 

   //add vertex to the vertex pst
   pubpc void addVertex(char label){
      lstVertices[vertexCount++] = new Vertex(label);
   }

   //add edge to edge array
   pubpc void addEdge(int start,int end){
      adjMatrix[start][end] = 1;
      adjMatrix[end][start] = 1;
   }

   //display the vertex
   pubpc void displayVertex(int vertexIndex){
      System.out.print(lstVertices[vertexIndex].label+" ");
   }       

   //get the adjacent unvisited vertex
   pubpc int getAdjUnvisitedVertex(int vertexIndex){
      for(int i=0; i<vertexCount; i++)
         if(adjMatrix[vertexIndex][i]==1 && lstVertices[i].visited==false)
            return i;
      return -1;
   }

   pubpc void depthFirstSearch(){
      //mark first node as visited
      lstVertices[0].visited = true;
      //display the vertex
      displayVertex(0);   
      //push vertex index in stack
      stack.push(0);

      while(!stack.isEmpty()){
         //get the unvisited vertex of vertex which is at top of the stack
         int unvisitedVertex = getAdjUnvisitedVertex(stack.peek());
         //no adjacent vertex found
         if(unvisitedVertex == -1){
            stack.pop();
         }else{
            lstVertices[unvisitedVertex].visited = true;
            displayVertex(unvisitedVertex);
            stack.push(unvisitedVertex);
         }
      }

      //stack is empty, search is complete, reset the visited flag        
      for(int i=0;i<vertexCount;i++){
         lstVertices[i].visited = false;
      }        
   }

   pubpc void breadthFirstSearch(){
      //mark first node as visited
      lstVertices[0].visited = true;
      //display the vertex
      displayVertex(0);   
      //insert vertex index in queue
      queue.insert(0);
      int unvisitedVertex;
      while(!queue.isEmpty()){
         //get the unvisited vertex of vertex which is at front of the queue
         int tempVertex = queue.remove();            
         //no adjacent vertex found
         while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){    
            lstVertices[unvisitedVertex].visited = true;
            displayVertex(unvisitedVertex);
            queue.insert(unvisitedVertex);               
         }
      }   

      //queue is empty, search is complete, reset the visited flag        
      for(int i=0;i<vertexCount;i++){
         lstVertices[i].visited = false;
      }    
   }
}

Demo Program

GraphDemo.java

package com.tutorialspoint.datastructure;

pubpc class GraphDemo {
   pubpc static void main(String args[]){
      Graph graph = new Graph();

      graph.addVertex( A );   //0
      graph.addVertex( B );   //1
      graph.addVertex( C );   //2
      graph.addVertex( D );   //3
      graph.addVertex( E );   //4
      graph.addVertex( F );   //5
      graph.addVertex( G );   //6

      /*       1  2  3   
       * 0  |--B--C--D
       * A--|
       * |
       * |     4 
       * |-----E
       * |     5  6
       * |  |--F--G
       * |--| 
       */        
      graph.addEdge(0, 1);   //AB
      graph.addEdge(1, 2);   //BC
      graph.addEdge(2, 3);   //CD
      graph.addEdge(0, 4);   //AC
      graph.addEdge(0, 5);   //AF
      graph.addEdge(5, 6);   //FG
      System.out.print("Depth First Search: ");
      //A B C D E F G
      graph.depthFirstSearch();        
      System.out.println("");
      System.out.print("Breadth First Search: ");
      //A B E F C G D
      graph.breadthFirstSearch();
   }
}

If we compile and run the above program then it would produce following result −

Depth First Search: A B C D E F G 
Breadth First Search: A B E F C G D