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

2024-08-31 17:12

本文主要是介绍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. 初始化省份计数器 count0
  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. 初始化省份计数器 count0
  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 = 1isConnected[0][1] == 1,合并城市0和城市1:
      • find(0) 返回 0, find(1) 返回 1。
      • 合并, parent[0] = 1parent = [1, 1, 2]
    • i = 0, j = 2isConnected[0][2] == 0,跳过。
    • i = 1, j = 2isConnected[1][2] == 0,跳过。
  • 遍历 parent 数组,统计根节点的数量:
    • parent = [1, 1, 2],根节点为 12,省份数量为 2

各方法的比较与选择

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

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

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



http://www.chinasem.cn/article/1124502

相关文章

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

CentOS 7部署主域名服务器 DNS的方法

《CentOS7部署主域名服务器DNS的方法》文章详细介绍了在CentOS7上部署主域名服务器DNS的步骤,包括安装BIND服务、配置DNS服务、添加域名区域、创建区域文件、配置反向解析、检查配置... 目录1. 安装 BIND 服务和工具2.  配置 BIND 服务3 . 添加你的域名区域配置4.创建区域

mss32.dll文件丢失怎么办? 电脑提示mss32.dll丢失的多种修复方法

《mss32.dll文件丢失怎么办?电脑提示mss32.dll丢失的多种修复方法》最近,很多电脑用户可能遇到了mss32.dll文件丢失的问题,导致一些应用程序无法正常启动,那么,如何修复这个问题呢... 在电脑常年累月的使用过程中,偶尔会遇到一些问题令人头疼。像是某个程序尝试运行时,系统突然弹出一个错误提

电脑提示找不到openal32.dll文件怎么办? openal32.dll丢失完美修复方法

《电脑提示找不到openal32.dll文件怎么办?openal32.dll丢失完美修复方法》openal32.dll是一种重要的系统文件,当它丢失时,会给我们的电脑带来很大的困扰,很多人都曾经遇到... 在使用电脑过程中,我们常常会遇到一些.dll文件丢失的问题,而openal32.dll的丢失是其中比较

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

Mysql中深分页的五种常用方法整理

《Mysql中深分页的五种常用方法整理》在数据量非常大的情况下,深分页查询则变得很常见,这篇文章为大家整理了5个常用的方法,文中的示例代码讲解详细,大家可以根据自己的需求进行选择... 目录方案一:延迟关联 (Deferred Join)方案二:有序唯一键分页 (Cursor-based Paginatio