*Connected Components in an Undirected Graph*

*Connected Components in an Undirected Graph*

Write a C Program to find Connected Components in an Undirected Graph. Here’s simple Program to Cout the Number of Connected Components in an Undirected Graph in C Programming Language.

## Undirected graph

An undirected graph is graph, i.e., a set of objects (called vertices or nodes) that are connected together, where all the edges are bidirectional. An undirected graph is sometimes called an undirected network. In contrast, a graph where the edges point in a direction is called a directed graph.

**Also Read : : C Program to find whether an Undirected Graph is Connected or not**

Below is the source code for C Program to find Connected Components in an Undirected Graph which is successfully compiled and run on Windows System to produce desired output as shown below :

**SOURCE CODE : :**

**SOURCE CODE : :**

/* C Program to find connected components in an Undirected Graph */ #include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define waiting 2 #define visited 3 int n; /*Number of vertices in the graph*/ int adj[MAX][MAX]; /*Adjacency Matrix*/ int state[MAX]; /*can be initial, waiting or visited*/ int label[MAX]; /*Denotes the Component Number*/ void create_graph(); void BF_Traversal(); void BFS(int v, int component_Num); int queue[MAX], front = -1,rear = -1; void insert_queue(int vertex); int delete_queue(); int isEmpty_queue(); int main() { create_graph(); BF_Traversal(); }/*End of main()*/ void BF_Traversal() { int v, components = 0; for(v=0;v<n;v++) state[v] = initial; components++; BFS(0, components); /*start BFS from vertex 0*/ for(v=0; v<n; v++) { if(state[v] == initial) { components++; BFS(v, components); } } printf("\nNumber of connected components = %d\n", components); if(components == 1) printf("\nConnected Graph\n"); else printf("\nNot a Connected Graph\n"); }/*End of BF_Traversal()*/ void BFS(int v, int component_Num) { int i; insert_queue(v); state[v] = waiting; while(!isEmpty_queue()) { v = delete_queue(); state[v] = visited; label[v] = component_Num; printf("\nVertex %d Component = %d\n",v, label[v]); for(i=0; i<n; i++) { /* Check for adjacent unvisited vertices */ if( adj[v][i] == 1 && state[i] == initial) { insert_queue(i); state[i] = waiting; } } } printf("\n"); }/*End of BFS()*/ void insert_queue(int vertex) { if (rear == MAX-1) printf("Queue Overflow\n"); else { if(front == -1) /*If queue is initially empty */ front = 0; rear = rear+1; queue[rear] = vertex ; } }/*End of insert_queue()*/ int isEmpty_queue() { if(front == -1 || front > rear ) return 1; else return 0; }/*End of isEmpty_queue()*/ int delete_queue() { int del_item; if (front == -1 || front > rear) { printf("\nQueue Underflow\n"); exit(1); } del_item = queue[front]; front = front+1; return del_item; }/*End of delete_queue() */ void create_graph() { int i,max_edges,origin,destin; printf("\nEnter number of vertices : "); scanf("%d",&n); max_edges = n*(n-1)/2; /*Undirected graph*/ for(i=1;i<=max_edges;i++) { printf("\nEnter edge %d( -1 -1 to quit ) : ",i); scanf("%d %d",&origin,&destin); if((origin == -1) && (destin == -1)) break; if( origin >= n || destin >= n || origin<0 || destin<0) { printf("\nInvalid edge!\n"); i--; } else { adj[origin][destin]=1; adj[destin][origin]=1; } }/*End of for*/ }/*End of create_graph()*/

**OUTPUT : :**

**OUTPUT : :**

/* C Program to find connected components in an Undirected Graph */ Enter number of vertices : 6 Enter edge 1( -1 -1 to quit ) : 0 1 Enter edge 2( -1 -1 to quit ) : 0 2 Enter edge 3( -1 -1 to quit ) : 0 3 Enter edge 4( -1 -1 to quit ) : 1 3 Enter edge 5( -1 -1 to quit ) : 3 2 Enter edge 6( -1 -1 to quit ) : -1 -1 Vertex 0 Component = 1 Vertex 1 Component = 1 Vertex 2 Component = 1 Vertex 3 Component = 1 Vertex 4 Component = 2 Vertex 5 Component = 3 Number of connected components = 3 Not a Connected Graph Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may * Contact Us* through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.

**Thanks for reading the post…**

**Recommended Posts : :**

**Recommended Posts : :**

- Undirected Graph is Connected or not
- Traversing an Undirected Graph through BFS
- BFS Algorithm for Connected Graph
- BFS Algorithm for Disconnected Graph
- Path Matrix by Warshall’s Algorithm