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.
package com.maixuanviet.graph; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class DTGraph { 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; DTGraph() { 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 CheckDirectedGraphisTree { 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(DTGraph 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(DTGraph 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(DTGraph 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) { DTGraph g = new DTGraph(); g.read_CCGraph(true); 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 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.
Related posts:
Hướng dẫn sử dụng Lớp FilePermission trong java
Java InputStream to String
List Interface trong Java
Build a REST API with Spring and Java Config
Encode/Decode to/from Base64
Allow user:password in URL
Java Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach
Feign – Tạo ứng dụng Java RESTful Client
A Custom Media Type for a Spring REST API
Validate email address exists or not by Java Code
Java Program to Find the Vertex Connectivity of a Graph
Spring Boot - Database Handling
Hướng dẫn Java Design Pattern – Builder
Wrapper Classes in Java
Spring Boot - Zuul Proxy Server and Routing
Tạo ứng dụng Java RESTful Client với thư viện Retrofit
DynamoDB in a Spring Boot Application Using Spring Data
Giới thiệu HATEOAS
Comparing Dates in Java
Basic Authentication with the RestTemplate
Introduction to Spring Boot CLI
Java String Conversions
Derived Query Methods in Spring Data JPA Repositories
A Guide to EnumMap
Constructor Injection in Spring with Lombok
Java Program to Implement Brent Cycle Algorithm
Anonymous Classes in Java
Simultaneous Spring WebClient Calls
Weak References in Java
A Guide to Concurrent Queues in Java
Java Program to Implement LinkedBlockingDeque API
Java Program to Implement Graph Coloring Algorithm