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:
Check If a String Is Numeric in Java
SOAP Web service: Authentication trong JAX-WS
Notify User of Login From New Device or Location
Transaction Propagation and Isolation in Spring @Transactional
Guide to Java OutputStream
The Dining Philosophers Problem in Java
Giới thiệu luồng vào ra (I/O) trong Java
How to Manually Authenticate User with Spring Security
Guava – Join and Split Collections
Migrating from JUnit 4 to JUnit 5
Debug a JavaMail Program
Java Program for Topological Sorting in Graphs
Java Program to Implement RenderingHints API
Java Program to Implement Ternary Search Algorithm
Java – Convert File to InputStream
How to Get the Last Element of a Stream in Java?
Converting String to Stream of chars
OAuth 2.0 Resource Server With Spring Security 5
Java Program to Perform Matrix Multiplication
Java Program to Implement Floyd-Warshall Algorithm
Guide to UUID in Java
Java Program to Find Path Between Two Nodes in a Graph
Send email with SMTPS (eg. Google GMail)
Java Program to Implement Best-First Search
Java Program to Implement Sorted Singly Linked List
How to Store Duplicate Keys in a Map in Java?
Multi Dimensional ArrayList in Java
Guide to Spring 5 WebFlux
Introduction to Spring Security Expressions
Spring Security and OpenID Connect
Spring Security OAuth2 – Simple Token Revocation
Introduction to Spliterator in Java