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:
Annotation trong Java 8
Check if there is mail waiting
Getting Started with Custom Deserialization in Jackson
Immutable ArrayList in Java
Comparing Long Values in Java
Java – Reader to InputStream
Apache Commons Collections Bag
Predicate trong Java 8
Java Program to Perform Polygon Containment Test
New Features in Java 13
Spring RequestMapping
Uploading MultipartFile with Spring RestTemplate
Java Program to Implement Hash Tables with Linear Probing
Hướng dẫn Java Design Pattern – Composite
Java Program to Find Transpose of a Graph Matrix
Guide to @JsonFormat in Jackson
Một số tính năng mới về xử lý ngoại lệ trong Java 7
Guide to the Java Clock Class
Java Program to Implement HashSet API
Spring Boot With H2 Database
Spring Security OAuth2 – Simple Token Revocation
Allow user:password in URL
Flattening Nested Collections in Java
Java Program to Implement Graph Coloring Algorithm
Java Program to Implement Borwein Algorithm
A Quick Guide to Using Keycloak with Spring Boot
Getting Started with GraphQL and Spring Boot
Java Program to Implement Min Heap
Guava – Join and Split Collections
Lớp Collectors trong Java 8
Map to String Conversion in Java
How to Get a Name of a Method Being Executed?