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:
Java Program to Implement Selection Sort
Kết hợp Java Reflection và Java Annotations
Làm thế nào tạo instance của một class mà không gọi từ khóa new?
Java Program to Generate a Random Subset by Coin Flipping
Java Program to Print only Odd Numbered Levels of a Tree
Introduction to Spring Cloud Rest Client with Netflix Ribbon
Generating Random Numbers in a Range in Java
Consumer trong Java 8
A Guide to the ResourceBundle
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Java Program to Implement ConcurrentSkipListMap API
Spring Boot: Customize the Jackson ObjectMapper
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
So sánh ArrayList và LinkedList trong Java
Lớp lồng nhau trong java (Java inner class)
Paint the edges of the tree
Java Program to Represent Linear Equations in Matrix Form
Hướng dẫn Java Design Pattern – Null Object
Object Type Casting in Java
Java Program to Perform Left Rotation on a Binary Search Tree
The Difference Between Collection.stream().forEach() and Collection.forEach()
Spring Boot - Unit Test Cases
RegEx for matching Date Pattern in Java
Marker Interface trong Java
Find the Registered Spring Security Filters
Java Program to Implement Graph Coloring Algorithm
Database Migrations with Flyway
Guide to the Synchronized Keyword in Java
Java Program to Implement Flood Fill Algorithm
What is Thread-Safety and How to Achieve it?
Java Program to Implement Interpolation Search Algorithm
Hướng dẫn Java Design Pattern – Bridge