面试必看：省份数量-平芜编程栈

【详细解析】LeetCode省份数量问题（BFS解法）

在日常的算法学习中，图论相关的基础问题是绕不开的重点，其中“省份数量”这个经典问题既能帮助我们理解图的连通性概念，也能巩固广度优先遍历（BFS）的核心思想。今天就带着大家一步步拆解这个问题，从题目理解到代码实现，把每个细节都讲清楚。

一、题目完整解读

首先我们先把题目要求理解透彻，避免因为审题不清导致解题方向出错：
给定n个城市，它们之间的连接关系用一个n * n的二维矩阵isConnected表示：

isConnected[i][j] = 1：第i个城市和第j个城市直接相连；
isConnected[i][j] = 0：第i个城市和第j个城市不直接相连。

同时满足“传递性”：如果城市a连b，b连c，那么a和c属于同一组相连城市。我们把“一组直接或间接相连的城市”定义为一个“省份”，要求计算给定矩阵中一共有多少个这样的省份。

举个简单例子帮助理解：
当n=3，isConnected = [[1,1,0],[1,1,0],[0,0,1]]时：

城市0和城市1互相连接，属于1个省份；
城市2单独成一个省份；
最终结果就是2个省份。

二、问题核心分析

这个问题本质上是求解无向图的连通分量个数：

每个城市可以看作图中的一个“节点”；
城市间的直接连接关系就是节点间的“边”；
我们需要统计图中有多少个相互独立的连通区域（省份）。

解题的关键在于：

标记已经访问过的节点（城市），避免重复统计；
遍历所有节点，对每个未访问的节点，通过遍历找到其所有连通节点，完成一个省份的统计。

三、算法选择思路

对于连通分量的统计，最常用的两种基础算法是深度优先遍历（DFS）和广度优先遍历（BFS）：

DFS：从一个节点出发，沿着一条路径走到头，再回溯处理其他分支；
BFS：从一个节点出发，先处理当前节点的所有相邻节点，再逐层向外扩展。

两种算法都能解决这个问题，今天我们重点讲解BFS解法，因为BFS的“逐层遍历”特性更符合直观的“找相连城市”的思路，也更容易通过队列的操作理解遍历过程。

四、BFS解题思路拆解

我们可以把整个解题过程拆解为几个清晰的步骤，一步一步来实现：

步骤1：初始化关键变量

定义visited布尔数组：长度为n，visited[i] = true表示第i个城市已被访问，初始值全为false；
定义队列q：用于存储待处理的城市节点，实现BFS的逐层遍历；
定义ans变量：用于统计省份数量，初始值为0。

步骤2：遍历所有城市

逐个检查每个城市i：

如果visited[i] = false，说明这是一个新的省份的起点：
- 省份数量ans加1；
- 标记visited[i] = true，并将该城市加入队列；
处理队列中的所有相连城市：
- 取出队列头部的城市index；
- 遍历index对应的一行连接关系，找到所有和index直接相连且未被访问的城市；
- 将这些城市标记为已访问，并加入队列等待后续处理；
当队列为空时，说明当前省份的所有相连城市都已遍历完成，继续检查下一个未访问的城市。

步骤3：返回结果

遍历完所有城市后，ans的值就是最终的省份数量。

五、完整可运行代码

#include<iostream>#include<vector>#include<queue>usingnamespacestd;classSolution{public:intfindCircleNum(vector<vector<int>>&isConnected){// 获取城市的数量nintn=isConnected.size();// 统计省份数量intans=0;// BFS使用的队列，存储待处理的城市索引queue<int>q;// 标记城市是否被访问过，避免重复统计vector<bool>visited(n,false);// 遍历每一个城市for(inti=0;i<n;i++){// 如果当前城市未被访问，说明是新省份的起点if(!visited[i]){visited[i]=true;// 标记为已访问ans++;// 省份数量加1q.push(i);// 将当前城市加入队列// 处理当前省份的所有相连城市while(!q.empty()){// 取出队列头部的城市索引intindex=q.front();q.pop();// 遍历当前城市的所有连接关系for(intj=0;j<n;j++){// 条件：和当前城市直接相连、未被访问、不是自身if(isConnected[index][j]==1&&!visited[j]&&j!=index){visited[j]=true;// 标记为已访问q.push(j);// 加入队列继续处理}}}}}returnans;}};// 测试示例，方便验证代码正确性intmain(){Solution solution;// 测试用例1：2个省份vector<vector<int>>test1={{1,1,0},{1,1,0},{0,0,1}};cout<<"测试用例1结果："<<solution.findCircleNum(test1)<<endl;// 测试用例2：1个省份vector<vector<int>>test2={{1,0,0,1},{0,1,1,0},{0,1,1,1},{1,0,1,1}};cout<<"测试用例2结果："<<solution.findCircleNum(test2)<<endl;return0;}