C++ Program to Check if a Graph is Connected

Table of Contents

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.
Depth-First Search (DFS): An algorithm for traversing or searching tree or graph data structures.
Breadth-First 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 Depth-First Search (DFS) or Breadth-First 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:

C++

    (A)---(B)
     |     |
    (C)---(D)

C++ Program

C++

#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

C++

Graph is connected.

Example 2: Disconnected Graph Using BFS

Graph Representation

Consider a graph with five vertices where not all vertices are connected:

C++

    (A)   (B)
     |     |
    (C)   (D)
           |
          (E)

C++ Program

C++

#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

C++

Graph is not connected.

Example 3: Larger Connected Graph Using DFS

Graph Representation

Consider a larger graph with six vertices:

C++

    (A)---(B)---(C)
     |     |     |
    (D)---(E)---(F)

C++ Program

C++

#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

C++

Graph is connected.

Conclusion

Checking if a graph is connected is a fundamental task in graph theory with wide-ranging 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++