This is a java program In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. A graph that is itself connected has exactly one connected component, consisting of the whole graph.
Here is the source code of the Java Program to Find the Connected Components of an UnDirected Graph. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
// Sample program to find connected components of undirected graph package com.maixuanviet.graph; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class CCGraph { 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; CCGraph() { 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 ConnectedComponents { 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(CCGraph 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(CCGraph 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 void connected_components(CCGraph 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"); } } } static public void main(String[] args) { CCGraph g = new CCGraph(); g.read_CCGraph(false); g.print_CCGraph(); connected_components(g); } }
Output:
$ javac ConnectedComponents.java $ java ConnectedComponents 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 3 6 4 1: 2 2: 4 3 1 3: 6 2 4: 6 5 2 5: 6 4 6: 4 3 5 Component 1: 1 2 4 3 6 5 Enter the number of vertices: 6 Enter the number of edges: 7 Enter the edges: <from> <to> 1 2 1 4 1 3 2 3 5 6 6 5 4 3 1: 3 4 2 2: 3 1 3: 4 2 1 4: 3 1 5: 6 6 6: 5 5 Component 1: 1 3 4 2 Component 2: 5 6
Related posts:
Sắp xếp trong Java 8
Spring Data JPA Delete and Relationships
Spring Boot - Interceptor
Java Program to Implement Shoelace Algorithm
HashSet trong java
Guide to Java 8’s Collectors
Disable Spring Data Auto Configuration
Java – File to Reader
Java Program to Implement Flood Fill Algorithm
Java Program to Implement the Program Used in grep/egrep/fgrep
Intro to the Jackson ObjectMapper
Java Program to Check Whether an Input Binary Tree is the Sub Tree of the Binary Tree
Java Program to Implement Multi-Threaded Version of Binary Search Tree
Java Program to Implement the One Time Pad Algorithm
Hướng dẫn Java Design Pattern – Composite
Java Program to Implement Fermat Factorization Algorithm
Instance Profile Credentials using Spring Cloud
Handle EML file with JavaMail
Copy a List to Another List in Java
Adding a Newline Character to a String in Java
Introduction to Spring Cloud CLI
Hướng dẫn Java Design Pattern – Chain of Responsibility
Hướng dẫn Java Design Pattern – Abstract Factory
Check If Two Lists are Equal in Java
Spring REST API + OAuth2 + Angular
Integer Constant Pool trong Java
Connect through a Proxy
Java CyclicBarrier vs CountDownLatch
Lập trình đa luồng với CompletableFuture trong Java 8
Java Program to Find MST (Minimum Spanning Tree) using Prim’s Algorithm
Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach
Constructor Dependency Injection in Spring