如何判断图连通c++代码

在C++中，判断无向图是否连通通常会采用深度优先搜索(DFS)或广度优先搜索(BFS)算法。以下是两种常见的方法：

1. **深度优先搜索 (DFS)**:

#include <vector>
using namespace std;

bool is_connected(vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    return dfs(graph, start, visited);
}

// DFS 函数
bool dfs(vector<vector<int>>& graph, int node, vector<bool>& visited) {
    visited[node] = true;
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            if (!dfs(graph, neighbor, visited)) return false; // 如果邻接节点不可达，则整个图不连通
        } else {
            // 避免环路影响判断，如果已经访问过则跳过
        }
    }
    
    return true; // 当前节点可达，继续检查下一个未访问的节点
}

2. **广度优先搜索 (BFS)**:

#include <queue>

bool is_connected_bfs(vector<vector<int>>& graph, int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    q.push(start);

    while (!q.empty()) {
        int size = q.size();
        for (size_t i = 0; i < size; ++i) {
            int curr = q.front(); q.pop();
            visited[curr] = true;

            for (int neighbor : graph[curr])
                if (!visited[neighbor])
                    q.push(neighbor);
        }

        if (visited.size() == graph.size()) break; // 找到所有节点则返回true，表示连通
    }

    return visited.size() == graph.size(); // 图完全连通时返回true，否则false
}

**