Introduction
In graph theory, checking whether a graph is connected is a fundamental task. A connected graph is one in which there is a path between any pair of vertices. This property is crucial for many applications, such as network design, communication, and transportation systems. This article will guide you through the process of checking if a graph is connected using C++, providing three distinct examples with solutions and outputs to illustrate different scenarios.
Prerequisites
Before we dive into the examples, itâ€™s important to understand the following concepts:
 Graph: A collection of nodes (vertices) and edges connecting some or all of them.
 Connected Graph: A graph is connected if there is a path between every pair of vertices.
 DepthFirst Search (DFS): An algorithm for traversing or searching tree or graph data structures.
 BreadthFirst Search (BFS): Another algorithm for traversing or searching tree or graph data structures.
Familiarity with C++ programming, including standard libraries like <iostream>
, <vector>
, and <queue>
, will be beneficial.
Checking Graph Connectivity
To check if a graph is connected, we can use either DepthFirst Search (DFS) or BreadthFirst Search (BFS). Both algorithms can traverse all vertices reachable from a starting vertex. If all vertices are visited, the graph is connected; otherwise, it is not.
Pseudocode for Checking Connectivity
 Initialize all vertices as not visited.
 Start from an arbitrary vertex and perform DFS or BFS.
 If all vertices are visited, the graph is connected.
 If any vertex is not visited, the graph is not connected.
Examples
Example 1: Simple Graph Using DFS
Graph Representation
Consider a simple graph with four vertices:
(A)(B)
 
(C)(D)
C++ Program
#include <iostream>
#include <vector>
using namespace std;
void DFS(int v, vector<vector<int>>& graph, vector<bool>& visited) {
visited[v] = true;
for (int i = 0; i < graph[v].size(); ++i) {
if (!visited[graph[v][i]]) {
DFS(graph[v][i], graph, visited);
}
}
}
bool isConnected(vector<vector<int>>& graph, int V) {
vector<bool> visited(V, false);
DFS(0, graph, visited);
for (int i = 0; i < V; ++i) {
if (!visited[i]) return false;
}
return true;
}
int main() {
int V = 4;
vector<vector<int>> graph(V);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(0);
graph[1].push_back(3);
graph[2].push_back(0);
graph[3].push_back(1);
if (isConnected(graph, V))
cout << "Graph is connected." << endl;
else
cout << "Graph is not connected." << endl;
return 0;
}
Output
Graph is connected.
Example 2: Disconnected Graph Using BFS
Graph Representation
Consider a graph with five vertices where not all vertices are connected:
(A) (B)
 
(C) (D)

(E)
C++ Program
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void BFS(int v, vector<vector<int>>& graph, vector<bool>& visited) {
queue<int> q;
visited[v] = true;
q.push(v);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < graph[u].size(); ++i) {
if (!visited[graph[u][i]]) {
visited[graph[u][i]] = true;
q.push(graph[u][i]);
}
}
}
}
bool isConnected(vector<vector<int>>& graph, int V) {
vector<bool> visited(V, false);
BFS(0, graph, visited);
for (int i = 0; i < V; ++i) {
if (!visited[i]) return false;
}
return true;
}
int main() {
int V = 5;
vector<vector<int>> graph(V);
graph[0].push_back(2);
graph[2].push_back(0);
graph[1].push_back(3);
graph[3].push_back(1);
graph[3].push_back(4);
graph[4].push_back(3);
if (isConnected(graph, V))
cout << "Graph is connected." << endl;
else
cout << "Graph is not connected." << endl;
return 0;
}
Output
Graph is not connected.
Example 3: Larger Connected Graph Using DFS
Graph Representation
Consider a larger graph with six vertices:
(A)(B)(C)
  
(D)(E)(F)
C++ Program
#include <iostream>
#include <vector>
using namespace std;
void DFS(int v, vector<vector<int>>& graph, vector<bool>& visited) {
visited[v] = true;
for (int i = 0; i < graph[v].size(); ++i) {
if (!visited[graph[v][i]]) {
DFS(graph[v][i], graph, visited);
}
}
}
bool isConnected(vector<vector<int>>& graph, int V) {
vector<bool> visited(V, false);
DFS(0, graph, visited);
for (int i = 0; i < V; ++i) {
if (!visited[i]) return false;
}
return true;
}
int main() {
int V = 6;
vector<vector<int>> graph(V);
graph[0].push_back(1);
graph[0].push_back(3);
graph[1].push_back(0);
graph[1].push_back(2);
graph[1].push_back(4);
graph[2].push_back(1);
graph[2].push_back(5);
graph[3].push_back(0);
graph[3].push_back(4);
graph[4].push_back(1);
graph[4].push_back(3);
graph[4].push_back(5);
graph[5].push_back(2);
graph[5].push_back(4);
if (isConnected(graph, V))
cout << "Graph is connected." << endl;
else
cout << "Graph is not connected." << endl;
return 0;
}
Output
Graph is connected.
Conclusion
Checking if a graph is connected is a fundamental task in graph theory with wideranging applications. By using algorithms such as DFS and BFS, we can efficiently determine the connectivity of a graph. Through the provided examples, we demonstrated different scenarios and how to implement connectivity checks in C++