• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Aug 20th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
2.
3. public class CheckIfGraphIsTree {
4.
5.     static class Graph {
6.         int vertices;
8.
9.         public Graph(int vertices) {
10.             this.vertices = vertices;
11.
13.             //Initialize lists
14.             for (int i = 0; i < vertices; i++) {
16.             }
17.         }
18.
19.         public void addEdge(int source, int destination) {
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++) {
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++) {
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);
100.             graph.checkifTree();
101.             System.out.println("----------------------------");
102.             Graph graph1 = new Graph(5);
108.             graph1.checkifTree();
109.             System.out.println("----------------------------");
110.             Graph graph2 = new Graph(5);