本文共 1332 字，大约阅读时间需要 4 分钟。

判断一个图是否为连通图

判断一个图是否为连通图的步骤如下：

示例代码：

#include 
   
    #include 
    
     using namespace std;int main() {    int n;    cin >> n;    vector
     
      
       > adj(n + 1);    for (int i = 1; i <= n; ++i) {        adj[i].reserve(n + 1);    }    for (int x, y; cin >> x >> y; ++adj[x].push_back(y), ++adj[y].push_back(x)) {        if (x < 1 || x > n || y < 1 || y > n) {            // 处理无效顶点，跳过            continue;        }    }    vector
       
         visit(n + 1, false);    stack
        
          stack; visit[1] = true; stack.push(1); bool connected = true; while (!stack.empty()) { int current = stack.top(); stack.pop(); for (int neighbor : adj[current]) { if (!visit[neighbor]) { visit[neighbor] = true; stack.push(neighbor); } } } for (int i = 1; i <= n; ++i) { if (!visit[i]) { connected = false; break; } } cout << (connected ? 1 : 0);}
        
       
      
     
    
   

代码解释：

• 输入处理：读取顶点数 n 和边的信息，构建邻接表 adj。
• 初始化访问数组：visit 记录每个顶点是否被访问，初始时只有顶点 1 被标记为已访问。
• DFS遍历：使用栈结构从顶点 1 开始遍历所有可达顶点，标记访问状态。
• 结果判断：检查所有顶点是否被访问。如果有未被访问的顶点，图不连通，输出 0；否则，输出 1。

通过以上方法，可以准确判断给定图是否为连通图。

转载地址：http://rwye.baihongyu.com/