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

323.无向图中连通分量的数目(bfs)323. 无向图中连通分量的数目 leetcode原题链接:https://leetcode-cn.com/problems/number-of-connected-components-in-an-

Offer 驾到,掘友接招!我正在参与2022春招打卡活动,点击查看活动详情

不是因为看到了希望才坚持,而是因为坚持了才能看到希望。共勉

每日刷题第54天 2021.03.03

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

题目描述

  • 你有一个包含 n 个节点的图。给定一个整数 n 和一个数组 edges ,其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。
  • 返回图中已连接分量的数目。

示例

  • 示例1 image.png
输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
输出: 2
  • 示例2 image.png
输入: 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]]
    • 因此这里:判断的时候,将当前固定的节点和下一条边的xy分别进行比较,如果有相同的,则可以相连,那么就将当前的边连接顺序修改过来(主要是考虑到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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注