企业官网建设流程全解析

LeetCode 547 Friend Circles 题解：邻接矩阵到无向图连通分量的三种解法（DFS / BFS / Union-Find）

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文基于本仓库 problems/547.friend-circles-en.md 及配套资料，系统讲解 LeetCode 547「朋友圈（Friend Circles / 省份数量）」这道经典图论题：给定一个 N×N 的学生好友关系矩阵，求所有"朋友圈"（即直接或间接好友构成的连通团体）总数。读完本文，你将掌握如何把邻接矩阵转化为无向图模型，以及求解连通分量数量的三种标准算法 ——DFS、BFS、带按秩合并的 Union-Find（并查集），并看到每种思路的完整可运行代码、复杂度分析与本仓库源码级佐证。

问题描述

原题链接见 problems/547.friend-circles-en.md（LeetCode 上该题现已更名为 547. Number of Provinces，仓库中文版见 problems/547.number-of-provinces.md）。

班上有 N 名学生，其中有些人是朋友，有些不是，且友谊具有传递性：如果 A 是 B 的直接朋友，B 是 C 的直接朋友，那么 A 是 C 的间接朋友。所谓"朋友圈"，是指一组直接或间接互为朋友的学生。

给定一个 N×N 矩阵 M 表示学生间的好友关系：

• M[i][j] = 1表示第 i 个与第 j 个学生是直接朋友；
• 否则为 0。

要求输出所有学生中朋友圈的总数。

示例 1：

输入: [[1,1,0], [1,1,0], [0,0,1]] 输出: 2 解释: 学生 0 和学生 1 是直接朋友，属于同一个朋友圈；学生 2 自己单独构成一个朋友圈，因此返回 2。

示例 2：

输入: [[1,1,0], [1,1,1], [0,1,1]] 输出: 1 解释: 学生 0 与学生 1 直接相连，学生 1 与学生 2 直接相连，因此学生 0 与学生 2 是间接朋友，三人同属一个朋友圈，返回 1。

约束条件：

• N 的取值范围为 [1, 200]；
• 对所有学生有M[i][i] = 1（自己与自己当然是"朋友"）；
• 若M[i][j] = 1，则必有M[j][i] = 1（好友关系是对称的）。

注意：约束 2、3 决定了 M 是一个对称矩阵，这正是无向图邻接矩阵的特征，也是下面三种算法得以成立的前提。

问题建模：把邻接矩阵转化为无向图

原文档给出的第一个关键洞察是：把矩阵 M 视为一张无向图的邻接矩阵（Adjacency Matrix）。矩阵的行列下标 i、j 就是图的 N 个顶点，M[i][j] = 1表示顶点 i 与顶点 j 之间存在一条无向边。于是"朋友圈的数量"就等价于该无向图中连通分量（connected components）的数量。

如上图所示（仓库中的示意图 assets/problems/547.friend-circle-1.png）：一个 5×5 的对称邻接矩阵，右侧对应一张无向图 —— 节点 0、1、2、3 通过边连成一片（0-1、0-2、1-3），节点 4 孤立存在。整张图共有 2 个连通分量，也就是 2 个朋友圈。

一旦完成这个转化，问题就落入图论中非常成熟的求解范畴。原文档明确指出，连通分量问题通常可以用DFS、BFS、Union-Find三种方法解决，下文逐一展开。

解法一：DFS（深度优先搜索）

思路

DFS 求解连通分量的做法非常直观：

1. 从每一个节点出发做一次 DFS，用visited数组标记已访问节点；
2. 每轮 DFS 中，递归访问当前节点所有直接相连且未访问的节点；
3. 一次完整的 DFS 恰好覆盖一个连通分量，因此统计发起 DFS 的次数，就是连通分量（朋友圈）的个数。

上图（assets/problems/547.friend-circle-dfs.png）展示了 DFS 的递归路径：从节点 0 出发沿 0→1→3→2 深度优先推进，途中用visited数组记录已访问节点；当第一个连通分量遍历完毕，再从未访问的节点 4 发起新一轮 DFS，最终统计出 2 个连通分量。

Java 实现

以下代码摘自原文档：

class FindCirclesDFS { public int findCircleNumDFS(int[][] M) { if (M == null || M.length == 0 || M[0].length == 0) return 0; int n = M.length; int numCircles = 0; boolean[] visited = new boolean[n]; for (int i = 0; i < n; i++) { if (!visited[i]) { dfs(M, i, visited, n); numCircles++; } } return numCircles; } private void dfs(int[][] M, int i, boolean[] visited, int n) { for (int j = 0; j < n; j++) { if (M[i][j] == 1 && !visited[j]) { visited[j] = true; dfs(M, j, visited, n); } } } }

仓库的每日一题 daily/2019-08-11.md 中给出了同思路的 Java DFS 实现，两者结构一致：外层循环枚举起点、内层递归沿邻接矩阵扩展。

复杂度分析

• 时间复杂度：O(n²)—— n 为学生数，最坏情况需遍历整个 n×n 矩阵；
• 空间复杂度：O(n)—— 大小为 n 的visited数组（递归深度最坏也是 O(n)）。

解法二：BFS（广度优先搜索 / 层级遍历）

思路

BFS 与 DFS 的区别在于遍历顺序：从某一起点出发，先访问其所有直接相邻节点（同一层），再逐层向外扩展：

1. 从某个未访问节点开始，借助队列访问它所有直接相连的节点，即同一"层级"的所有节点；
2. 用visited数组标记已访问节点；
3. 每当从新的起点发起一轮 BFS，计数加一 —— 每轮 BFS 覆盖一个连通分量。

上图（assets/problems/547.friend-circle-bfs.png）展示了 BFS 的分层推进：第一层只有节点 0，第二层是节点 1、2，第三层是节点 3，逐层扩散直到覆盖整个连通分量；随后从未访问的节点 4 开始新一轮 BFS，最终同样统计出 2 个连通分量。

Java 实现

以下代码摘自原文档：

class FindCircleBFS { public int findCircleNumBFS(int[][] M) { if (M == null || M.length == 0) return 0; int numCircle = 0; int n = M.length; boolean[] visited = new boolean[n]; Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < n; i++) { // already visited, skip if (visited[i]) continue; queue.add(i); while (!queue.isEmpty()) { int curr = queue.poll(); visited[curr] = true; for (int j = 0; j < n; j++) { if (M[curr][j] == 1 && !visited[j]) { queue.add(j); } } } numCircle++; } return numCircle; } }

需要注意一个细节：BFS 中节点curr入队后，其所有未访问的邻居会被批量入队，visited标记保证了节点不会重复入队，从而每轮外层while恰好处理一个连通分量。

复杂度分析

• 时间复杂度：O(n²)—— 遍历整个 n×n 矩阵；
• 空间复杂度：O(n)—— 队列与visited数组均为 n 规模。

解法三：Union-Find（并查集）

思路

并查集（Union-Find / Disjoint Set Union）是求解"连通分量个数"最经典的利器之一，原文档明确推荐使用它。核心思想：

1. 初始化parent数组，每个节点的父节点指向自己，即每个学生自成一个朋友圈；
2. 遍历矩阵，对所有直接相连的节点对执行union，使两个节点归属于同一个根节点；
3. 每成功合并一次，朋友圈计数减一；
4. 全部遍历结束后，count就是朋友圈总数。

初始: parent = [0,1,2,3,4], count = 5 union(0,1) -> count = 4 union(0,2) -> count = 3 union(1,3) -> count = 2 结果: 连通分量 = 2（{0,1,2,3} 与 {4}）

上图（assets/problems/547.friend-circle-uf.png）展示了并查集的合并轨迹：每执行一次union，count减一，右侧树状结构直观呈现了 0、1、2、3 逐渐归并为同一根节点、4 独立的过程，最终连通分量数为 2。

原文档特别强调，这里使用的是weighted-union-find（按秩/按规模合并的并查集），以避免union和find在最坏情况下退化到 O(n) 的线性时间。

Java 实现

以下代码摘自原文档：

class FindCircleUF { public int findCircleNumUF(int[][] M) { if (M == null || M.length == 0 || M[0].length == 0) return 0; int n = M.length; UnionFind uf = new UnionFind(n); for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // union friends if (M[i][j] == 1) { uf.union(i, j); } } } return uf.count; } } class UnionFind { int count; int[] parent; int[] rank; public UnionFind(int n) { count = n; parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } } public int find(int a) { return parent[a] == a ? a : find(parent[a]); } public void union(int a, int b) { int rootA = find(a); int rootB = find(b); if (rootA == rootB) return; if (rank[rootA] <= rank[rootB]) { parent[rootA] = rootB; rank[rootB] += rank[rootA]; } else { parent[rootB] = rootA; rank[rootA] += rank[rootB]; } count--; } public int count() { return count; } }

注意两个实现细节：

• 遍历矩阵时只需遍历上三角（j从i+1开始），因为矩阵对称，M[i][j]与M[j][i]等价，可减少一半的合并尝试；
• rank数组记录每棵"树"的规模，union时把规模小的树挂到规模大的树上，保证树高可控。

复杂度分析

• 时间复杂度：O(n²·log n)—— 遍历 n×n 矩阵，配合加权并查集，单次union/find为 O(log n)；
• 空间复杂度：O(n)——parent与rank数组均为 n 规模。

深入：并查集的底层原理与优化

find / union / connected 三大核心操作

本仓库的并查集专题 thinkings/union-find.md 对该数据结构做了系统讲解。它使用树型结构处理不交集（Disjoint Sets）的合并与查询问题，核心是三个 API：

• find(x)：沿parent链向上查找 x 所属集合的根（代表元素）。递归写法parent[x] == x ? x : find(parent[x])与循环写法等价；
• connected(p, q)：判断两个元素是否连通，即find(p) == find(q)；
• union(p, q)：将两个集合合并，即把其中一个的根挂到另一个的根上，并使连通分量计数减一。

两种关键优化

thinkings/union-find.md明确指出，并查集的时间消耗主要在union和find，若不优化，树高可能退化为节点数，find的时间复杂度退化到 O(n)。两种标准优化手段是：

1. 路径压缩（Path Compression）：在find过程中把沿途节点直接指向根，将树高压低。例如递归写法：

def find(self, x): if x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] return x

2. 按秩合并（Union by Rank / Size）：union时把小树挂到大树上，让合并后的树尽量平衡。本仓库 thinkings/union-find.md 给出的 Python 模板如下：

class UF: def __init__(self, M): self.parent = {} self.size = {} self.cnt = 0 for i in range(M): self.parent[i] = i self.cnt += 1 self.size[i] = 1 def find(self, x): if x != self.parent[x]: self.parent[x] = self.find(self.parent[x]) return self.parent[x] return x def union(self, p, q): if self.connected(p, q): return leader_p = self.find(p) leader_q = self.find(q) if self.size[leader_p] < self.size[leader_q]: self.parent[leader_p] = leader_q self.size[leader_q] += self.size[leader_p] else: self.parent[leader_q] = leader_p self.size[leader_p] += self.size[leader_q] self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q)

同时使用路径压缩与按秩合并时，时间复杂度可趋近 O(1)（严格表述是 O(m·α(n))，α 为阿克曼函数的反函数）；只使用其中一种时，复杂度为 O(log n) 级别。这也印证了原文档对加权并查集复杂度的分析。

中文版 Python 解法

中文题解 problems/547.number-of-provinces.md 给出了更简洁的 Python 版本（未做路径压缩与按秩合并，最坏 O(N)），代码可直接运行：

class UF: parent = {} cnt = 0 def __init__(self, M): n = len(M) for i in range(n): self.parent[i] = i self.cnt += 1 def find(self, x): while x != self.parent[x]: x = self.parent[x] return x def union(self, p, q): if self.connected(p, q): return self.parent[self.find(p)] = self.find(q) self.cnt -= 1 def connected(self, p, q): return self.find(p) == self.find(q) class Solution: def findCircleNum(self, M: List[List[int]]) -> int: n = len(M) uf = UF(M) for i in range(n): for j in range(i): if M[i][j] == 1: uf.union(i, j) return uf.cnt

该解法的时间复杂度平均 O(log N)、最坏 O(N)，空间复杂度 O(N)（parent数组）；若补上路径压缩与按秩合并即可将时间稳定在近似 O(1) 级别。

每日一题中的 C++ 并查集写法

仓库每日一题 daily/2019-08-11.md 还提供了一份 C++ 实现，其find中pre[x] = find(pre[x], pre)即典型的路径压缩写法，并采用"每成功合并一对朋友 group 减一"的计数策略：

class Solution { public: int findCircleNum(vector<vector<int>>& M) { if (M.empty()) return 0; vector<int> pre(M.size()); for(int i=0; i<M.size(); i++) pre[i] = i;//先各自为组，组名也为自己的序号 int group = M.size();//一开始有多少人就有多少个朋友圈，当每出现一对朋友时就减1，最后就是总的朋友圈数量了。 for(int i=0; i<M.size(); i++) { for(int j=0; j<M.size(); j++) { if (i != j && M[i][j] == 1) { int x1 = find(i, pre);//x1为i所属的组 int x2 = find(j, pre);//x2为j所属的组 if (x1 != x2) { //如果不属于同个朋友圈的话就把i归为j的组 pre[x1] = x2; group--; } } } } return group; } private: int find(int x, vector<int>& pre) { //"pre[x] = "这句为路径压缩，直接指向组的根节点，下次查询时就快很多了。 return pre[x]==x ? x : pre[x] = find(pre[x], pre); } };

三种语言（Java / Python / C++）的并查集实现共享同一套逻辑骨架：初始化自环 parent → 遍历对称矩阵合并相连节点 → 返回剩余连通分量数。

关键要点总结

原文档在最后浓缩了本题的三个关键点，也是同类连通分量题的通法：

1. 把邻接矩阵转化为图模型—— 对称矩阵M[i][j] == 1即无向边，这是建模的核心一步；
2. 识别问题的本质—— 求朋友圈数量实际上就是求无向图连通分量数量；
3. 掌握连通分量问题的三种解法—— DFS、BFS、Union-Find 均可胜任，按需选用：
   • 实现最简洁的是 DFS（递归天然契合图的深搜）；
   • 需要显式层级遍历时选 BFS；
   • 需要频繁动态合并、查询连通性时选并查集（配合路径压缩与按秩合并）。

补充一点实战经验：DFS / BFS 遍历的是"未访问节点"视角，适合一次性求出全部连通分量；并查集则天然支持边不断加入时的增量式合并，在需要中途回答"当前有多少个连通块"的动态场景中更具优势。

相似题目与延伸阅读

相似题目（来自原文档）：

• 323. Number of Connected Components in an Undirected Graph—— 直接求无向图连通分量个数，是本题去掉"邻接矩阵"包装后的裸题；
• 1101. The Earliest Moment When Everyone Become Friends—— 好友关系按时间逐步建立，求所有人成为朋友的时刻，可用并查集维护连通分量数，典型增量合并场景。

仓库内延伸阅读：

• thinkings/union-find.md —— 并查集专题：find / union / connected 三大 API、路径压缩、按秩合并、带权并查集模板及复杂度证明；
• thinkings/DFS.md —— 深度优先遍历专题，含 DFS 通用算法模板（visited 标记 + 递归扩展）；
• problems/547.number-of-provinces.md —— 本题中文版题解（547. 省份数量），含 Python 实现与复杂度分析；
• daily/2019-08-11.md —— 每日一题「547. 朋友圈」，含 C++ 并查集与 Java DFS 两种参考实现。

仓库 README 中关于本题的索引见 README.md（0547. 省份数量 条目）。掌握"矩阵 → 图 → 连通分量"这条转化链路后，你就能在大量图论题中快速复用 DFS、BFS 与并查集这三板斧。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode