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 an UnDirected 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.
package com.maixuanviet.graph; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class TGraph { static final int MAXV = 100; static final int MAXDEGREE = 50; public int edges[][] = new int[MAXV + 1][MAXDEGREE]; public int degree[] = new int[MAXV + 1]; public int nvertices; public int nedges; TGraph() { nvertices = nedges = 0; for (int i = 1; i <= MAXV; i++) degree[i] = 0; } void read_CCGraph(boolean directed) { int x, y; Scanner sc = new Scanner(System.in); System.out.println("Enter the number of vertices: "); nvertices = sc.nextInt(); System.out.println("Enter the number of edges: "); int m = sc.nextInt(); System.out.println("Enter the edges: <from> <to>"); for (int i = 1; i <= m; i++) { x = sc.nextInt(); y = sc.nextInt(); insert_edge(x, y, directed); } sc.close(); } void insert_edge(int x, int y, boolean directed) { if (degree[x] > MAXDEGREE) System.out.printf( "Warning: insertion (%d, %d) exceeds max degree\n", x, y); edges[x][degree[x]] = y; degree[x]++; if (!directed) insert_edge(y, x, true); else nedges++; } void print_CCGraph() { for (int i = 1; i <= nvertices; i++) { System.out.printf("%d: ", i); for (int j = degree[i] - 1; j >= 0; j--) System.out.printf(" %d", edges[i][j]); System.out.printf("\n"); } } } public class CheckUndirectedGraphisTree { static final int MAXV = 100; static boolean processed[] = new boolean[MAXV]; static boolean discovered[] = new boolean[MAXV]; static int parent[] = new int[MAXV]; static void bfs(TGraph g, int start) { Queue<Integer> q = new LinkedList<Integer>(); int i, v; q.offer(start); discovered[start] = true; while (!q.isEmpty()) { v = q.remove(); // process_vertex(v); processed[v] = true; for (i = g.degree[v] - 1; i >= 0; i--) { if (!discovered[g.edges[v][i]]) { q.offer(g.edges[v][i]); discovered[g.edges[v][i]] = true; parent[g.edges[v][i]] = v; } } } } static void initialize_search(TGraph g) { for (int i = 1; i <= g.nvertices; i++) { processed[i] = discovered[i] = false; parent[i] = -1; } } static void process_vertex(int v) { System.out.printf(" %d", v); } static int connected_components(TGraph g) { int c; initialize_search(g); c = 0; for (int i = 1; i <= g.nvertices; i++) { if (!discovered[i]) { c++; // System.out.printf("Component %d:", c); bfs(g, i); // System.out.printf("\n"); } } return c; } static public void main(String[] args) { TGraph g = new TGraph(); g.read_CCGraph(false); g.print_CCGraph(); boolean flag = false; if (g.nedges == g.nvertices - 1) { flag = true; if (connected_components(g) == 1 && flag == true) { System.out .println("Graph is a Tree, as graph is connected and Euler's criterion is satisfied."); } } else { System.out .println("Graph is not a Tree, as Euler's criterion is not satisfied"); } } }
Output:
$ javac CheckUndirectedGraphisTree.java $ java CheckUndirectedGraphisTree 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 1 3: 6 2 4: 6 5 2 5: 6 4 6: 3 4 5 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 2 1 3 2 4 1: 3 2 2: 4 1 3: 1 4: 2 Graph is a Tree, as graph is connected and Euler's criterion is satisfied.
Related posts:
Spring WebClient Requests with Parameters
Control the Session with Spring Security
Hướng dẫn Java Design Pattern – Command
File Upload with Spring MVC
Getting Started with Custom Deserialization in Jackson
How to Return 404 with Spring WebFlux
Default Password Encoder in Spring Security 5
Java Convenience Factory Methods for Collections
Jackson – JsonMappingException (No serializer found for class)
Converting between an Array and a List in Java
Java Program to Implement Max-Flow Min-Cut Theorem
Apache Commons Collections BidiMap
Java Program to Print only Odd Numbered Levels of a Tree
Java Program to Implement vector
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Intro to Inversion of Control and Dependency Injection with Spring
Hướng dẫn Java Design Pattern – Bridge
An Intro to Spring Cloud Contract
Spring Webflux and CORS
Converting Between an Array and a Set in Java
Java CyclicBarrier vs CountDownLatch
Spring’s RequestBody and ResponseBody Annotations
Java Program to Implement Ternary Tree
Removing all Nulls from a List in Java
Spring Boot - Build Systems
Introduction to Spring Cloud OpenFeign
Java Program to Find Strongly Connected Components in Graphs
Guide to WeakHashMap in Java
Java Program to Implement Borwein Algorithm
Java Program to Perform Stooge Sort
Guide to DelayQueue
Java Program to Implement Stack using Linked List