SHARE
TWEET

Untitled

a guest Aug 20th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.LinkedList;
  2.  
  3. public class CheckIfGraphIsTree {
  4.  
  5.     static class Graph {
  6.         int vertices;
  7.         LinkedList<Integer>[] adjList;
  8.  
  9.         public Graph(int vertices) {
  10.             this.vertices = vertices;
  11.  
  12.             adjList = new LinkedList[vertices];
  13.             //Initialize lists
  14.             for (int i = 0; i < vertices; i++) {
  15.                 adjList[i] = new LinkedList<>();
  16.             }
  17.         }
  18.  
  19.         public void addEdge(int source, int destination) {
  20.             //add forward edge
  21.             adjList[source].addFirst(destination);
  22.             //add backward edge
  23.             adjList[destination].addFirst(source);
  24.         }
  25.  
  26.         public void checkifTree(){
  27.  
  28.             printGraph();
  29.  
  30.             //If cycle is not present and graph is connected, its a tree
  31.  
  32.             //create visited array
  33.             boolean [] visited = new boolean[vertices];
  34.  
  35.             //DFS for original graph start from first vertex
  36.             boolean isCycle = isCycleUtil(0, visited, -1);
  37.  
  38.             if(isCycle){
  39.                 //graph is disconnected, its not tree
  40.                 System.out.println("Given Graph is not Tree");
  41.                 return;
  42.             }
  43.  
  44.             //check the visited array to determine graph is connected or not
  45.             for (int i = 0; i <vertices ; i++) {
  46.                 if(!visited[i]) {
  47.                     System.out.println("Given Graph is not Tree");
  48.                     return;
  49.                 }
  50.             }
  51.             //if here, means graph is tree
  52.                 System.out.println("Given Graph is Tree");
  53.         }
  54.  
  55.         boolean isCycleUtil(int currVertex, boolean [] visited, int parent){
  56.  
  57.             //add this vertex to visited vertex
  58.             visited[currVertex] = true;
  59.  
  60.             //visit neighbors except its direct parent
  61.             for (int i = 0; i <adjList[currVertex].size() ; i++) {
  62.                 int vertex = adjList[currVertex].get(i);
  63.                 //check the adjacent vertex from current vertex
  64.                 if(vertex!=parent) {
  65.                     //if destination vertex is not its direct parent then
  66.                     if(visited[vertex]){
  67.                         //if here means this destination vertex is already visited
  68.                         //means cycle has been detected
  69.                         return true;
  70.                     }
  71.                     else{
  72.                         //recursion from destination node
  73.                         if (isCycleUtil(vertex, visited, currVertex)) {
  74.                             return true;
  75.                         }
  76.                     }
  77.                 }
  78.             }
  79.             return false;
  80.         }
  81.  
  82.         public void printGraph(){
  83.             for (int i = 0; i <vertices ; i++) {
  84.                 LinkedList<Integer> nodeList = adjList[i];
  85.                 System.out.println("Vertex connected from vertex: "+i);
  86.  
  87.                 for (int j = 0; j <nodeList.size() ; j++) {
  88.                     System.out.print("->" + nodeList.get(j));
  89.                 }
  90.                 System.out.println();
  91.             }
  92.         }
  93.  
  94.         public static void main(String[] args) {
  95.             Graph graph = new Graph(5);
  96.             graph.addEdge(1,0);
  97.             graph.addEdge(3,1);
  98.             graph.addEdge(3,2);
  99.             graph.addEdge(3,4);
  100.             graph.checkifTree();
  101.             System.out.println("----------------------------");
  102.             Graph graph1 = new Graph(5);
  103.             graph.addEdge(1,0);
  104.             graph.addEdge(3,1);
  105.             graph.addEdge(3,2);
  106.             graph.addEdge(3,4);
  107.             graph.addEdge(4,0);
  108.             graph1.checkifTree();
  109.             System.out.println("----------------------------");
  110.             Graph graph2 = new Graph(5);
  111.             graph2.addEdge(1,0);
  112.             graph2.addEdge(3,1);
  113.             graph2.addEdge(3,2);
  114.             graph2.checkifTree();
  115.         }
  116.     }
  117. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top