Find Undirected Graph is Connected or not
Write a C Program to find whether an Undirected Graph is Connected or not. Here’s simple C Program to find whether an Undirected Graph is Connected or not.
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 implement BFS Algorithm for Disconnected Graph
Below is the source code for C Program to find whether an Undirected Graph is Connected or not which is successfully compiled and run on Windows System to produce desired output as shown below :
SOURCE CODE : :
/* C Program to find whether an Undirected Graph is Connected or not */ #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*/ void create_graph(); void BF_Traversal(); void BFS(int v); int queue[MAX], front = -1,rear = -1; void insert_queue(int vertex); int delete_queue(); int isEmpty_queue(); int main() { create_graph(); BF_Traversal(); return 0; }/*End of main()*/ void BF_Traversal() { int v; int connected = 1; for(v=0; v<n; v++) state[v] = initial; BFS(0); /*start BFS from vertex 0*/ for(v=0; v<n; v++) { if(state[v] == initial) { connected = 0; break; } } if(connected) printf("\nGraph is connected\n"); else printf("\nGraph is not connected\n"); }/*End of BF_Traversal()*/ void BFS(int v) { int i; insert_queue(v); state[v] = waiting; while( !isEmpty_queue() ) { v = delete_queue( ); state[v] = visited; printf("%d ",v); for(i=0; i<=n-1; 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("\nQueue 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; 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 : :
/* C Program to find whether an Undirected Graph is Connected or not */ Enter number of vertices : 5 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 ) : 4 4 Enter edge 7( -1 -1 to quit ) : -1 -1 0 1 2 3 Graph is not connected 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 : :
- Traversing an Undirected Graph through BFS
- BFS Algorithm for Connected Graph
- BFS Algorithm for Disconnected Graph
- Path Matrix by Warshall’s Algorithm
- Path Matrix by powers of Adjacency matrix