Java Program to Check if a Graph is a Tree or Not using DFS

This is a java program to check if graph is tree or not. Graph is tree if,
1. It has number of edges one less than number of vertices.
2. Graph is connected.
3. There are no cycles.

Here is the source code of the Java Program to Check if a Directed Graph is a Tree or Not Using DFS. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.graph;
  3.  
  4. import java.util.LinkedList;
  5. import java.util.Queue;
  6. import java.util.Scanner;
  7.  
  8. class DTGraph
  9. {
  10.     static final int MAXV      = 100;
  11.     static final int MAXDEGREE = 50;
  12.     public int       edges[][] = new int[MAXV + 1][MAXDEGREE];
  13.     public int       degree[]  = new int[MAXV + 1];
  14.     public int       nvertices;
  15.     public int       nedges;
  16.  
  17.     DTGraph()
  18.     {
  19.         nvertices = nedges = 0;
  20.         for (int i = 1; i <= MAXV; i++)
  21.             degree[i] = 0;
  22.     }
  23.  
  24.     void read_CCGraph(boolean directed)
  25.     {
  26.         int x, y;
  27.         Scanner sc = new Scanner(System.in);
  28.         System.out.println("Enter the number of vertices: ");
  29.         nvertices = sc.nextInt();
  30.         System.out.println("Enter the number of edges: ");
  31.         int m = sc.nextInt();
  32.         System.out.println("Enter the edges: <from> <to>");
  33.         for (int i = 1; i <= m; i++)
  34.         {
  35.             x = sc.nextInt();
  36.             y = sc.nextInt();
  37.             insert_edge(x, y, directed);
  38.         }
  39.         sc.close();
  40.     }
  41.  
  42.     void insert_edge(int x, int y, boolean directed)
  43.     {
  44.         if (degree[x] > MAXDEGREE)
  45.             System.out.printf(
  46.                     "Warning: insertion (%d, %d) exceeds max degree\n", x, y);
  47.         edges[x][degree[x]] = y;
  48.         degree[x]++;
  49.         if (!directed)
  50.             insert_edge(y, x, true);
  51.         else
  52.             nedges++;
  53.     }
  54.  
  55.     void print_CCGraph()
  56.     {
  57.         for (int i = 1; i <= nvertices; i++)
  58.         {
  59.             System.out.printf("%d: ", i);
  60.             for (int j = degree[i] - 1; j >= 0; j--)
  61.                 System.out.printf(" %d", edges[i][j]);
  62.             System.out.printf("\n");
  63.         }
  64.     }
  65. }
  66.  
  67. public class CheckDirectedGraphisTree
  68. {
  69.     static final int MAXV         = 100;
  70.     static boolean   processed[]  = new boolean[MAXV];
  71.     static boolean   discovered[] = new boolean[MAXV];
  72.     static int       parent[]     = new int[MAXV];
  73.  
  74.     static void bfs(DTGraph g, int start)
  75.     {
  76.         Queue<Integer> q = new LinkedList<Integer>();
  77.         int i, v;
  78.         q.offer(start);
  79.         discovered[start] = true;
  80.         while (!q.isEmpty())
  81.         {
  82.             v = q.remove();
  83.             // process_vertex(v);
  84.             processed[v] = true;
  85.             for (i = g.degree[v] - 1; i >= 0; i--)
  86.             {
  87.                 if (!discovered[g.edges[v][i]])
  88.                 {
  89.                     q.offer(g.edges[v][i]);
  90.                     discovered[g.edges[v][i]] = true;
  91.                     parent[g.edges[v][i]] = v;
  92.                 }
  93.             }
  94.         }
  95.     }
  96.  
  97.     static void initialize_search(DTGraph g)
  98.     {
  99.         for (int i = 1; i <= g.nvertices; i++)
  100.         {
  101.             processed[i] = discovered[i] = false;
  102.             parent[i] = -1;
  103.         }
  104.     }
  105.  
  106.     static void process_vertex(int v)
  107.     {
  108.         System.out.printf(" %d", v);
  109.     }
  110.  
  111.     static int connected_components(DTGraph g)
  112.     {
  113.         int c;
  114.         initialize_search(g);
  115.         c = 0;
  116.         for (int i = 1; i <= g.nvertices; i++)
  117.         {
  118.             if (!discovered[i])
  119.             {
  120.                 c++;
  121.                 // System.out.printf("Component %d:", c);
  122.                 bfs(g, i);
  123.                 // System.out.printf("\n");
  124.             }
  125.         }
  126.         return c;
  127.     }
  128.  
  129.     static public void main(String[] args)
  130.     {
  131.         DTGraph g = new DTGraph();
  132.         g.read_CCGraph(true);
  133.         g.print_CCGraph();
  134.         boolean flag = false;
  135.         if (g.nedges == g.nvertices - 1)
  136.         {
  137.             flag = true;
  138.             if (connected_components(g) == 1 && flag == true)
  139.             {
  140.                 System.out
  141.                         .println("Graph is a Tree, as graph is connected and Euler's criterion is satisfied.");
  142.             }
  143.         }
  144.         else
  145.         {
  146.             System.out
  147.                     .println("Graph is not a Tree, as Euler's criterion is not satisfied.");
  148.         }
  149.     }
  150. }

Output:

$ javac CheckDirectedGraphisTree.java
$ java CheckDirectedGraphisTree
 
Enter the number of vertices: 
6
Enter the number of edges: 
7
Enter the edges: <from> <to>
1 2
2 3
2 4
4 5
5 6
6 4
6 3
1:  2
2:  4 3
3: 
4:  5
5:  6
6:  3 4
Graph is not a Tree, as Euler's criterion is not satisfied.
 
Enter the number of vertices: 
4
Enter the number of edges: 
3
Enter the edges: <from> <to>
1 3
1 2
3 4
1:  2 3
2: 
3:  4
4: 
Graph is a Tree, as graph is connected and Euler's criterion is satisfied.

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.