DFS、BFS、Union-Find：找出图中省份数量的最佳方法

本文主要是介绍DFS、BFS、Union-Find：找出图中省份数量的最佳方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目理解

问题描述：

• 有 n 个城市，其中一些城市之间直接相连，另一些则不相连。
• 如果城市 a 和城市 b 直接相连，且城市 b 和城市 c 直接相连，那么城市 a 和城市 c 间接相连。
• 省份被定义为一组直接或间接相连的城市，组内不包含与之不相连的其他城市。
• 给定一个 n x n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，isConnected[i][j] = 0 表示不直接相连。
• 需要返回矩阵中省份的数量。

示例解释：

• 示例 1：

  输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
  输出：2
  

  解释：城市1和城市2直接相连，城市3独自一省。

• 示例 2：

  输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
  输出：3
  

  解释：每个城市都独自一省。

547. 省份数量 - 力扣（LeetCode）

解决思路

这个问题实际上是在求图中的连通分量数量。每个省份对应于图中的一个连通分量。我们可以将城市看作图中的节点，直接相连表示节点之间有边。

有几种常见的方法可以求解连通分量：

1. 深度优先搜索（DFS）
2. 广度优先搜索（BFS）
3. 并查集（Union-Find）

我们将详细介绍这三种方法，并探讨它们的优缺点和实际应用场景。

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

思路：

• 遍历每个城市，如果该城市未被访问过，则开始一次DFS遍历，标记所有与之连通的城市为已访问。
• 每进行一次DFS遍历，省份数量加一。

步骤：

1. 初始化一个访问数组 visited，大小为 n，全部设为 false。
2. 初始化省份计数器 count 为 0。
3. 遍历每个城市 i：
   • 如果 visited[i] 为 false，则：
     • 进行一次DFS，从城市 i 开始，标记所有连通的城市为已访问。
     • 省份计数器 count 增加 1。
4. 返回 count 作为省份的数量。

实现代码：

#include <vector>using namespace std;class Solution {
public:void dfs(int i, vector<vector<int>>& isConnected, vector<bool>& visited) {visited[i] = true;for(int j = 0; j < isConnected.size(); j++) {if(isConnected[i][j] == 1 && !visited[j]) {dfs(j, isConnected, visited);}}}int findCircleNum(vector<vector<int>>& isConnected) {int n = isConnected.size();vector<bool> visited(n, false);int count = 0;for(int i = 0; i < n; i++) {if(!visited[i]) {dfs(i, isConnected, visited);count++;}}return count;}
};

代码解释：

• dfs 函数用于深度优先搜索，标记所有与当前城市 i 直接或间接相连的城市。
• 在 findCircleNum 函数中，遍历每个城市，如果未被访问，则调用 dfs 并增加省份计数。

优点：

• 易于理解和实现：DFS方法非常直观，尤其是对那些习惯递归思维的程序员来说。通过简单的递归调用就可以完成连通分量的遍历和计数。
• 适合稀疏图：对于大部分节点之间没有直接连接的图，DFS的性能表现良好。

缺点：

• 递归深度限制：在处理特别大的图时，递归深度可能会导致栈溢出，进而程序崩溃。在这种情况下，需要转换为迭代实现，或者增加栈的大小。

实际应用场景：

• 图的连通分量：DFS可以广泛应用于需要识别图中连通分量的问题中，比如社交网络中的群体识别、地图中区域的划分等。

示例讲解：

以示例1为例：

isConnected = [[1,1,0],[1,1,0],[0,0,1]]

• 初始化 visited = [false, false, false]，count = 0。
• 遍历城市0：
  • visited[0] 为 false，调用 dfs(0)。
    • 标记 visited[0] = true。
    • 检查城市0的连接：
      • 城市0与城市1相连，且 visited[1] = false，调用 dfs(1)。
        • 标记 visited[1] = true。
        • 检查城市1的连接：
          • 城市1与城市0相连，但 visited[0] = true。
          • 城市1与城市1相连，但自身已访问。
      • 城市0与城市2不相连。
    • dfs(0) 完成，count = 1。
• 遍历城市1：
  • visited[1] = true，跳过。
• 遍历城市2：
  • visited[2] = false，调用 dfs(2)。
    • 标记 visited[2] = true。
    • 检查城市2的连接：
      • 城市2与城市2相连，但自身已访问。
    • dfs(2) 完成，count = 2。
• 最终返回 2。

方法二：广度优先搜索（BFS）

思路：

与DFS类似，BFS也是用于遍历图中所有连通的节点。不同之处在于，DFS使用栈（递归实现），而BFS使用队列。这使得BFS能够层层推进，逐步扩展搜索范围，从起点节点开始，首先访问其所有邻接节点，然后再访问这些邻接节点的邻接节点，依此类推。

步骤：

1. 初始化一个访问数组 visited，大小为 n，全部设为 false。
2. 初始化省份计数器 count 为 0。
3. 遍历每个城市 i：
   • 如果 visited[i] 为 false，则：
     • 进行一次BFS，从城市 i 开始，标记所有连通的城市为已访问。
     • 省份计数器 count 增加 1。
4. 返回 count 作为省份的数量。

实现代码：

#include <vector>
#include <queue>using namespace std;class Solution {
public:int findCircleNum(vector<vector<int>>& isConnected) {int n = isConnected.size();vector<bool> visited(n, false);int count = 0;queue<int> q;for(int i = 0; i < n; i++) {if(!visited[i]) {q.push(i);while(!q.empty()) {int current = q.front();q.pop();if(!visited[current]) {visited[current] = true;for(int j = 0; j < n; j++) {if(isConnected[current][j] == 1 && !visited[j]) {q.push(j);}}}}count++;}}return count;}
};

代码解释：

• 使用队列 q 来实现BFS。
• 对于每个未访问的城市，加入队列，并依次访问其所有直接相连的城市，标记为已访问。

优点：

• 避免栈溢出：与DFS相比，BFS的迭代实现避免了深度递归可能带来的栈溢出问题，因此在处理大型图时更加稳定。
• 按层次遍历：BFS按层次遍历所有节点，能够保证先访问的节点离起点最近，这在某些特定问题中非常有用，比如求最短路径等。

缺点：

• 空间复杂度较高：BFS需要维护一个队列，因此在空间上比

DFS略显不足，特别是在图的节点较多且连通性较高时，队列的最大长度会增大，导致内存占用增加。

实际应用场景：

• 图的广度优先遍历：BFS广泛应用于各种图遍历任务中，尤其是那些要求按距离优先访问节点的任务，如最短路径问题、层次遍历等。

示例讲解：

以示例1为例：

isConnected = [[1,1,0],[1,1,0],[0,0,1]]

• 初始化 visited = [false, false, false]，count = 0。
• 遍历城市0：
  • visited[0] 为 false，将城市0加入队列 q。
  • BFS开始：
    • q 中有城市0，弹出 current = 0。
    • 标记 visited[0] = true。
    • 检查城市0的连接：
      • 城市0与城市1相连，将城市1加入队列 q。
    • q 中有城市1，弹出 current = 1。
    • 标记 visited[1] = true。
    • 检查城市1的连接：
      • 城市1与城市0相连，但 visited[0] = true。
    • BFS结束，count = 1。
• 遍历城市1：
  • visited[1] = true，跳过。
• 遍历城市2：
  • visited[2] = false，将城市2加入队列 q。
  • BFS开始：
    • q 中有城市2，弹出 current = 2。
    • 标记 visited[2] = true。
    • 检查城市2的连接：
      • 城市2与城市2相连，但自身已访问。
    • BFS结束，count = 2。
• 最终返回 2。

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

思路：

并查集是一种数据结构，常用于处理不相交集合的合并和查询问题。对于图中的连通分量问题，使用并查集可以高效地合并连通的节点，并在最后通过集合的数量来得出连通分量的数量。

步骤：

1. 初始化一个并查集 parent 数组，每个城市的父节点指向自己。
2. 遍历 isConnected 矩阵，对于每个直接相连的城市对 (i, j)：
   • 如果 isConnected[i][j] == 1，则合并城市 i 和城市 j。
3. 遍历所有城市，统计根节点的数量，即为省份的数量。

实现代码：

#include <vector>using namespace std;class Solution {
public:int find(int x, vector<int>& parent) {if(parent[x] != x) {parent[x] = find(parent[x], parent); // 路径压缩}return parent[x];}void unionSets(int x, int y, vector<int>& parent) {int rootX = find(x, parent);int rootY = find(y, parent);if(rootX != rootY) {parent[rootX] = rootY; // 合并集合}}int findCircleNum(vector<vector<int>>& isConnected) {int n = isConnected.size();vector<int> parent(n);for(int i = 0; i < n; i++) {parent[i] = i; // 初始化每个城市的父节点为自己}for(int i = 0; i < n; i++) {for(int j = i + 1; j < n; j++) {if(isConnected[i][j] == 1) {unionSets(i, j, parent);}}}int count = 0;for(int i = 0; i < n; i++) {if(parent[i] == i) {count++;}}return count;}
};

代码解释：

• find 函数用于查找某个城市的根节点，并通过路径压缩优化查找效率。
• unionSets 函数用于合并两个城市所属的集合。
• 最后遍历 parent 数组，统计根节点的数量即为省份数量。

优点：

• 高效处理连通性问题：并查集非常适合处理动态连通性问题，在合并和查找操作上都能保持较高的效率，尤其适合处理大规模图。
• 路径压缩和按秩合并：通过路径压缩和按秩合并优化，并查集在实际应用中非常高效，几乎达到了常数级别的性能。

缺点：

• 实现复杂度较高：相较于DFS和BFS，并查集的实现较为复杂，理解并查集的操作对于初学者来说可能有一定的难度。

实际应用场景：

• 动态连通性：并查集常用于解决动态连通性问题，例如网络中设备的连接性判断、社交网络中的群组划分等。

示例讲解：

以示例1为例：

isConnected = [[1,1,0],[1,1,0],[0,0,1]]

• 初始化 parent = [0, 1, 2]。
• 遍历 isConnected 矩阵：
  • i = 0, j = 1， isConnected[0][1] == 1，合并城市0和城市1：
    • find(0) 返回 0， find(1) 返回 1。
    • 合并， parent[0] = 1，parent = [1, 1, 2]。
  • i = 0, j = 2， isConnected[0][2] == 0，跳过。
  • i = 1, j = 2， isConnected[1][2] == 0，跳过。
• 遍历 parent 数组，统计根节点的数量：
  • parent = [1, 1, 2]，根节点为 1 和 2，省份数量为 2。

各方法的比较与选择

• DFS：适合稀疏图，代码简单易实现，但递归深度受限。
• BFS：适合处理递归深度受限的问题，按层次遍历，空间复杂度略高。
• 并查集：最优解法，适合大规模图，处理动态连通性问题高效，但实现复杂度较高。

在实际应用中，根据问题规模和图的稠密程度选择合适的方法。在省份问题中，如果图的规模较小且递归深度不是问题，DFS和BFS都是不错的选择；如果图的规模较大或需要频繁处理连通性问题，并查集则更为高效。

这篇关于DFS、BFS、Union-Find：找出图中省份数量的最佳方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---