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:
MyBatis with Spring
Marker Interface trong Java
Quản lý bộ nhớ trong Java với Heap Space vs Stack
Java Program to Implement Dijkstra’s Algorithm using Queue
Java Program to Implement Sorted Circularly Singly Linked List
Java Program to Permute All Letters of an Input String
Java Program to Encode a Message Using Playfair Cipher
Apache Commons Collections Bag
Quick Intro to Spring Cloud Configuration
Java Program to Implement Interval Tree
Loại bỏ các phần tử trùng trong một ArrayList như thế nào trong Java 8?
Hướng dẫn Java Design Pattern – DAO
Sử dụng CountDownLatch trong Java
Lớp HashMap trong Java
Spring MVC Tutorial
Spring Security Registration – Resend Verification Email
Java Program to Implement ConcurrentSkipListMap API
Introduction to PCollections
Jackson Annotation Examples
Hướng dẫn sử dụng Java Generics
Count Occurrences of a Char in a String
Guide to Spring 5 WebFlux
Xử lý ngoại lệ đối với trường hợp ghi đè phương thức trong java
Java Program to Implement Queue using Two Stacks
Checking for Empty or Blank Strings in Java
Performance Difference Between save() and saveAll() in Spring Data
Java Program to Implement Graph Structured Stack
LinkedHashSet trong java
Spring REST with a Zuul Proxy
Java Program to Construct an Expression Tree for an Prefix Expression
How to Change the Default Port in Spring Boot
Java Program to find the maximum subarray sum O(n^2) time(naive method)