CodeBrick 博客

Appearance

连通分量计数：DFS 数一遍 ​

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。连通分量是「图的基本概念」这一考点里最常在选择题里出现的概念之一，DFS/BFS 遍历图则是算法大题里反复用到的基本功。它是经典训练题，不是真题，也不押题。

题目 ​

给定一个含 n 个顶点的无向图 G（邻接矩阵或邻接表存储），设计算法求出 G 中连通分量的个数。

题面同样没有出现「尽可能高效」。按拓展训练导语的分类，这道题属于「直观即满分」型——直白的 DFS 遍历就是标准答案，力气花在把遍历写全、边界写对上。

直观解法：每个未访问顶点起一次 DFS ​

连通分量的定义就是「极大连通子图」。一次 DFS 从某个顶点出发，能走到的所有顶点都属于同一个连通分量。于是思路很直接：维护一个 visited 数组，依次检查每个顶点，遇到没访问过的就说明发现了一个新的连通分量，对它发起一次 DFS 把整块标记完，分量计数加一；直到所有顶点都被访问过。

c
#define MAXV 100

typedef struct {
    int numVertices;
    int Edge[MAXV][MAXV];   // 无向图邻接矩阵，Edge[i][j]==1 表示 i-j 之间有边
} MGraph;

void DFS(MGraph G, int v, int visited[]) {
    visited[v] = 1;
    for (int j = 0; j < G.numVertices; j++)
        if (G.Edge[v][j] && !visited[j])
            DFS(G, j, visited);
}

int countComponents(MGraph G) {
    int n = G.numVertices;
    int visited[MAXV] = {0};
    int count = 0;

    for (int v = 0; v < n; v++) {          // 外层遍历所有顶点，一个不漏
        if (!visited[v]) {
            DFS(G, v, visited);             // 从 v 出发标记整个连通块
            count++;                        // 起了一次 DFS，就多一个连通分量
        }
    }
    return count;
}

拿一个 6 顶点的图走一遍：{0,1,2} 三点互连、{3,4} 一条边、5 是孤立点。外层从 v=0 开始，DFS 把 0、1、2 全标记，count=1；v=1、v=2 已访问过跳过；v=3 未访问，DFS 把 3、4 标记，count=2；v=5 未访问，DFS 只标记它自己，count=3。最终返回 3，和直觉一致。

复杂度：邻接矩阵下，所有 DFS 调用加起来恰好把 n2 个矩阵元素扫一遍，时间 O(n2)；换成邻接表存储则是 O(n+e)。visited 数组占 O(n) 空间，递归栈最坏 O(n)。

为什么它就是满分解 ​

用总纲的「找浪费三问」审一遍：

  1. 有没有重复扫描？ 没有。visited 数组保证每个顶点只被标记一次、每条边只沿着遍历方向经过一次，不会有顶点被 DFS 进两次。
  2. 有没有重算已知的东西？ 没有。一个顶点一旦被标记，后续外层循环直接跳过，不会对它再发起一次 DFS。
  3. 有没有放着性质不用？ 没有。题目没给任何额外结构（有序、稀疏之类），邻接矩阵/邻接表已经是最基本的存储形式。

更根本的一条：要确认每个顶点属于哪个连通分量，至少要把图完整遍历一遍——邻接矩阵下这是 O(n2)、邻接表下是 O(n+e)，这正是该存储方式下的理论下界，不存在跳过某些顶点或边还能保证正确的写法。碰到下界，直观写法就是最优解。

真正的难点在这里 ​

分不在优化上，在三处容易漏的细节：

  • visited 数组必须全局共享，不能在 DFS 里重新声明。 如果把 visited 定义成 DFS 函数的局部变量，每次递归调用都会拿到一份「干净」的数组，不仅起不到标记作用，还会造成无穷递归。visited 要在 countComponents 里定义一次，整个遍历过程共用同一份。
  • 外层循环必须扫过所有顶点，一个不能漏。 图不一定连通，漏掉某个顶点的检查，就会漏数一个连通分量——尤其是孤立顶点（没有任何边的顶点），它自己就是一个独立的连通分量，DFS 对它调用一次、只标记它自己，同样要计入 count。
  • 别在同一个连通块里重复计数。 count++ 只应该发生在「外层循环发现一个未访问顶点」的那一刻，DFS 递归过程本身不能触发计数——递归调用只负责标记，不负责计数，这两件事分给了两处不同的代码，混在一起写容易多算。

DFS 数连通分量，看一遍 ​

用题面描述的 6 顶点图搭一个例子：0-1、1-2 构成一个三角块的两条边，3-4 是另一条独立边，顶点 5 完全孤立。演示外层依次检查顶点、DFS 标记连通块，最终数出 3 个连通分量：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。

别画蛇添足 ​

  • 别为了「优化」换成并查集。 并查集在处理动态加边（边一条条给出、随时要判断连通性）时确实比反复 DFS 更划算，但这道题的图是一次性给定的静态图，DFS/BFS 遍历一遍已经是下界，换成并查集不会更快，只会多写一套 find/union。
  • 别对每个顶点单独发起一次全图 DFS。 如果不用 visited 数组去重，而是「对每个顶点都从头 DFS 一遍、数它能到达多少点」，同一个连通分量会被反复遍历 n 次，退化成 O(n3)——纯属浪费。

下一步 ​

相关真题（1题）

2014Q42综合题10分
去刷题

> **总思路**：题面看似考网络，其实考的是**图的抽象 + 邻接表设计 + Dijkstra**——把 4 个路由器和 4 个直连子网当作图的顶点，链路当作

图基本概念邻接表Dijkstra 最短路径