【详细解析】LeetCode省份数量问题BFS解法在日常的算法学习中图论相关的基础问题是绕不开的重点其中“省份数量”这个经典问题既能帮助我们理解图的连通性概念也能巩固广度优先遍历BFS的核心思想。今天就带着大家一步步拆解这个问题从题目理解到代码实现把每个细节都讲清楚。一、题目完整解读首先我们先把题目要求理解透彻避免因为审题不清导致解题方向出错给定n个城市它们之间的连接关系用一个n * n的二维矩阵isConnected表示isConnected[i][j] 1第i个城市和第j个城市直接相连isConnected[i][j] 0第i个城市和第j个城市不直接相连。同时满足“传递性”如果城市a连bb连c那么a和c属于同一组相连城市。我们把“一组直接或间接相连的城市”定义为一个“省份”要求计算给定矩阵中一共有多少个这样的省份。举个简单例子帮助理解当n3isConnected [[1,1,0],[1,1,0],[0,0,1]]时城市0和城市1互相连接属于1个省份城市2单独成一个省份最终结果就是2个省份。二、问题核心分析这个问题本质上是求解无向图的连通分量个数每个城市可以看作图中的一个“节点”城市间的直接连接关系就是节点间的“边”我们需要统计图中有多少个相互独立的连通区域省份。解题的关键在于标记已经访问过的节点城市避免重复统计遍历所有节点对每个未访问的节点通过遍历找到其所有连通节点完成一个省份的统计。三、算法选择思路对于连通分量的统计最常用的两种基础算法是深度优先遍历DFS和广度优先遍历BFSDFS从一个节点出发沿着一条路径走到头再回溯处理其他分支BFS从一个节点出发先处理当前节点的所有相邻节点再逐层向外扩展。两种算法都能解决这个问题今天我们重点讲解BFS解法因为BFS的“逐层遍历”特性更符合直观的“找相连城市”的思路也更容易通过队列的操作理解遍历过程。四、BFS解题思路拆解我们可以把整个解题过程拆解为几个清晰的步骤一步一步来实现步骤1初始化关键变量定义visited布尔数组长度为nvisited[i] true表示第i个城市已被访问初始值全为false定义队列q用于存储待处理的城市节点实现BFS的逐层遍历定义ans变量用于统计省份数量初始值为0。步骤2遍历所有城市逐个检查每个城市i如果visited[i] false说明这是一个新的省份的起点省份数量ans加1标记visited[i] true并将该城市加入队列处理队列中的所有相连城市取出队列头部的城市index遍历index对应的一行连接关系找到所有和index直接相连且未被访问的城市将这些城市标记为已访问并加入队列等待后续处理当队列为空时说明当前省份的所有相连城市都已遍历完成继续检查下一个未访问的城市。步骤3返回结果遍历完所有城市后ans的值就是最终的省份数量。五、完整可运行代码#includeiostream#includevector#includequeueusingnamespacestd;classSolution{public:intfindCircleNum(vectorvectorintisConnected){// 获取城市的数量nintnisConnected.size();// 统计省份数量intans0;// BFS使用的队列存储待处理的城市索引queueintq;// 标记城市是否被访问过避免重复统计vectorboolvisited(n,false);// 遍历每一个城市for(inti0;in;i){// 如果当前城市未被访问说明是新省份的起点if(!visited[i]){visited[i]true;// 标记为已访问ans;// 省份数量加1q.push(i);// 将当前城市加入队列// 处理当前省份的所有相连城市while(!q.empty()){// 取出队列头部的城市索引intindexq.front();q.pop();// 遍历当前城市的所有连接关系for(intj0;jn;j){// 条件和当前城市直接相连、未被访问、不是自身if(isConnected[index][j]1!visited[j]j!index){visited[j]true;// 标记为已访问q.push(j);// 加入队列继续处理}}}}}returnans;}};// 测试示例方便验证代码正确性intmain(){Solution solution;// 测试用例12个省份vectorvectorinttest1{{1,1,0},{1,1,0},{0,0,1}};cout测试用例1结果solution.findCircleNum(test1)endl;// 测试用例21个省份vectorvectorinttest2{{1,0,0,1},{0,1,1,0},{0,1,1,1},{1,0,1,1}};cout测试用例2结果solution.findCircleNum(test2)endl;return0;}六、复杂度分析时间复杂度外层循环遍历所有n个城市内层嵌套循环会遍历每个城市对应的n个连接关系每个城市和每条连接关系只会被处理一次因此总时间复杂度为O(n²)。空间复杂度visited数组占用O(n)的空间队列的最大长度最坏情况下为n所有城市都相连因此总空间复杂度为O(n)原代码中“ON”是不规范写法修正为标准的O(n)。七、拓展思考如果要改用DFS解法只需要把队列替换为递归函数从一个未访问的城市出发递归访问所有相连的城市并标记这个问题还可以用“并查集Union-Find”解决适合处理大规模的连通性问题感兴趣的同学可以自行研究注意边界条件当n1时只有1个城市结果必然是1代码中也能正确处理这个情况。总结“省份数量”问题的核心是统计无向图的连通分量个数BFS是解决这类问题的基础方法BFS解法的关键是通过队列实现逐层遍历配合visited数组避免重复访问代码实现时要注意循环变量命名冲突、边界条件处理等细节保证代码的正确性和可读性。这个问题是图论入门的经典题目理解清楚BFS的遍历逻辑后再遇到类似的连通性问题比如岛屿数量就能举一反三了。如果有任何疑问欢迎在评论区交流讨论。