Offer 驾到,掘友接招!我正在参与2022春招打卡活动,点击查看活动详情。
不是因为看到了希望才坚持,而是因为坚持了才能看到希望。共勉
每日刷题第54天 2021.03.03
323. 无向图中连通分量的数目
- leetcode原题链接:leetcode-cn.com/problems/nu…
- 难度:中等
- 方法:bfs广度优先搜索
题目描述
- 你有一个包含
n
个节点的图。给定一个整数n
和一个数组edges
,其中edges[i] = [ai, bi]
表示图中ai
和bi
之间有一条边。 - 返回图中已连接分量的数目。
示例
- 示例1
输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
输出: 2
- 示例2
输入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
输出: 1
提示
- 1 <= n <= 2000
- 1 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= ai <= bi < n
- ai != bi
- edges 中不会出现重复的边
拓展知识(广度优先遍历)
- 生活中的例子:上大学的时候,上课有个笔记没有记录完整。你想要解决完善这个笔记,那么你就需要先询问自己班级上的同学,是否有人记了笔记(第一层);假如还是没有找到笔记的话,你就需要去询问这个老师教的其他班的学生是否有记笔记(第二层)。这样一层一层的解决问题,就是
bfs
。 - 实现的数据结构:队列
- 应用:无权图中找最短路径
- 在无权图中,由于广度优先遍历本身的特点,假设源点为source,只有在遍历到所有距离源点 source 的距离为 d 的所有结点以后,才能遍历到所有距离源点 source 的距离为 d + 1 的所有结点。
- 也可以使用「两点之间、线段最短」这条经验来辅助理解如下结论:从源点 source 到目标结点 target 走直线走过的路径一定是最短的。
- 注意事项:无权图中遍历,加入队列后必须马上标记为已访问
思路分析
- 既然
bfs
是一层一层的遍历,那么对于无向图中的每一个节点也可以进行一层层的遍历。 - 整体思想:(需要准备的参数)
- 使用
visited
数组记录已经遍历过的边,使用二维数组就可以visited[x][y] = 0 || 1
- 有可能存在单独的节点,没有边与其相连,根据题意其也算一个连通分量,因此需要使用
point
数组,将已经遍历过的节点记录下来,最终结果需要加上没有遍历过的节点数。
- 使用
- 循环遍历边数组,对于没有被标记(即没有走过的)边,将其放入
bfs
函数中。 bfs
函数:无权图中与当前节点开始或者结束的边,都属于第一层,将第一层的边依次压入到队列queue
中,记下第一层的长度后,开始for
循环遍历处于第一层的每一条边的下一个相连的边。- 寻找下一个相连的边的时候需要注意:有可能与上一条边相连的节点在
y
而不是x
,因为其是无权图,没有方向。样例:[[2,3],[1,2],[1,3]]
- 因此这里:判断的时候,将当前固定的节点和下一条边的
x
和y
分别进行比较,如果有相同的,则可以相连,那么就将当前的边连接顺序修改过来(主要是考虑到visited
数组的记录问题,才修改原字符串)。
- 寻找下一个相连的边的时候需要注意:有可能与上一条边相连的节点在
- 每次都将查到的可以相连的边放入到队列中,一层一层的这样向下遍历,最终会找完所有的无向图中的连通节点。
- 回顾:多个进行
bfs
的入口节点,有点类似多源bfs
。
AC
代码
var countComponents = function(n, edges) {
// 无向图 从一个节点遍历
// 遍历整个数组中的边
let ans = 0;
let len = edges.length;
let cha = n;
// if(n == 2) return 1;
// 其他的情况
let point = new Array(n).fill(0);
// 封装循环
let queue = new Array();
function cycle (x) {
for(let i = 0; i < len; i++) {
// 无向图需要遍历一些情况
// 目前思考的解法:只要有这个节点的都找出来
// 如果是在后面的那么就修改原数组,visited还是按原来的标记即可
if(edges[i][0] == x && visited[edges[i][0]][edges[i][1]] == 0){
queue.push(edges[i]);
visited[edges[i][0]][edges[i][1]] = 1;
}
if(edges[i][1] == x && visited[edges[i][0]][edges[i][1]] == 0) {
// 后面的值时当前的起点,需要变化数值,再存进去
let tempt = edges[i][0];
edges[i][0] = edges[i][1];
edges[i][1] = tempt;
queue.push(edges[i]);
visited[edges[i][0]][edges[i][1]] = 1;
}
}
}
function bfs(cur) {
// 当前作为第一层
queue.push(cur);
visited[cur[0]][cur[1]] = 1;
let x = cur[0];
// 遍历数组中是否还有相同的开头的节点
cycle(x);
// console.log('找到最初的',queue);
// 找到所有相同的节点
while(queue.length != 0) {
let curLen = queue.length;
for(let j = 0; j < curLen; j++) {
let front = queue.shift();
// console.log(front);
visited[front[0]][front[1]] = 1;
point[front[1]] = 1;
cycle(front[1]);
}
}
}
// 标记数组,记录当前的边是否跑过
let visited = new Array(n);
for(let i = 0; i < n; i++) {
visited[i] = new Array(n).fill(0);
}
for(let i = 0; i < len; i++) {
let x = edges[i][0];
let y = edges[i][1];
if(visited[x][y] == 0){
ans++;
point[x] = 1;
bfs(edges[i]);
}
}
for(let i = 0; i < n; i++) {
if(point[i] == 0) ans++;
}
// 遍历剩余开头节点全部为0
return ans;
};
总结
- 无向图的特征:
[2,1]和[1,2]
是一样的,因为不区分方向。
今天的文章323.无向图中连通分量的数目(bfs)分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/18062.html