C++中图的连通性如何判断

在C++中，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来判断图的连通性。以下是使用深度优先搜索算法判断无向图连通性的示例代码：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int start) {
    visited[start] = true;
    for (int i = 0; i < graph[start].size(); i++) {
        if (!visited[graph[start][i]]) {
            dfs(graph, visited, graph[start][i]);
        }
    }
}

bool isGraphConnected(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    
    dfs(graph, visited, 0);
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    
    return true;
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {0, 2},
        {0, 1, 3},
        {2}
    };
    
    if (isGraphConnected(graph)) {
        cout << "The graph is connected." << endl;
    } else {
        cout << "The graph is not connected." << endl;
    }
    
    return 0;
}

在上面的代码中，我们定义了一个dfs函数来进行深度优先搜索，然后通过遍历整个图，检查是否所有节点都被访问到来判断图的连通性。如果所有节点都被访问到，则图是连通的，否则图是不连通的。