📖本篇内容：leetcode每日一题323.无向图中连通分量的数目

📆 最近更新：2022年1月3日 leetcode每日一题1185. 一周中的第几天 枚举的简单题 还能更简单~你想到了么

🙊个人简介：一只二本院校在读的大三程序猿，本着注重基础，打卡算法，分享技术作为个人的经验总结性的博文博主，虽然可能有时会犯懒，但是还是会坚持下去的，如果你很喜欢博文的话，建议看下面一行~（疯狂暗示QwQ）

🌇 点赞 👍 收藏 ⭐留言 📝 一键三连 _{关爱程序猿，从你我做起}

写在前面

因为今天是猫抓老鼠的困难无向图题,所以咱们就来试试简单一点的bfs模板来入门广度优先算法这门说难不难，说简单不简单的模块吧~冲就完事了！

本文参阅了力扣与东哥的算法小抄的思路与解题模板~
如有需要请移步至东哥的公众号哦~

题目

323. 无向图中连通分量的数目

给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图中连通分量的数目。

示例

示例1：

输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]0          3|          |1 --- 2    4 输出: 2

示例2：

输入: n = 5 和 edges = [[0, 1], [1, 2], [2, 3], [3, 4]]0           4|           |1 --- 2 --- 3输出:  1

提示

你可以假设在 edges 中不会出现重复的边。而且由于所以的边都是无向边，[0, 1] 与 [1, 0] 相同，所以它们不会同时在 edges 中出现。

思路

在图中，由于 图中存在环，和深度优先遍历一样，广度优先遍历也需要在遍历的时候记录已经遍历过的结点。特别注意：将结点添加到队列以后，一定要马上标记为「已经访问」，否则相同结点会重复入队，这一点在初学的时候很容易忽略。如果很难理解这样做的必要性，建议大家在代码中打印出队列中的元素进行调试：在图中，如果入队的时候不马上标记为「已访问」，相同的结点会重复入队，这是不对的。

另外一点还需要强调，广度优先遍历用于求解「无权图」的最短路径，因此一定要认清「无权图」这个前提条件。如果是带权图，就需要使用相应的专门的算法去解决它们。事实上，这些「专门」的算法的思想也都基于「广度优先遍历」的思想。

话不多说上模板!!!

/*** @param adj     邻接表* @param u       从 u 这个顶点开始广度优先遍历* @param visited 全局使用的 visited 布尔数组*/private void bfs(List<Integer>[] adj, int u, boolean[] visited) {Queue<Integer> queue = new LinkedList<>();queue.offer(u);visited[u] = true;while (!queue.isEmpty()) {Integer front = queue.poll();// 获得队首结点的所有后继结点List<Integer> successors = adj[front];for (int successor : successors) {if (!visited[successor]) {queue.offer(successor);// 特别注意：在加入队列以后一定要将该结点标记为访问，否则会出现结果重复入队的情况visited[successor] = true;}}}}

代码实现

class Solution {public int countComponents(int n, int[][] edges) {//初始化图List<Integer>[] adj = new ArrayList[n];for (int i = 0;i < n;i++){adj[i] = new ArrayList<>();}//因为是无向图 所以双向引用for (int[] edge : edges){adj[edge[0]].add(edge[1]);adj[edge[1]].add(edge[0]);}//广度搜索遍历int res = 0 ;boolean[] visited = new boolean[n];for (int i = 0 ; i < n;i++){if (!visited[i]){bfs(adj,i,visited);res++;}}return res;}public void bfs(List<Integer>[] adj ,int i ,boolean[] visited){Queue<Integer> q = new LinkedList<>();q.offer(i);visited[i] = true;while(!q.isEmpty()){Integer front = q.poll();List<Integer> successors = adj[front];for(int successor : successors){if (!visited[successor]){q.offer(successor);visited[successor] = true;}}}}
}

执行结果

写在最后

今天是2022-01-04！，小付坚持打卡了哦~

主要是为了继续夯实bfs的基础知识

适用范围

最后

每天进步点 每天收获点

愿诸君 事业有成 学有所获

如果觉得不错 别忘啦一键三连哦~