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]是一样的，因为不区分方向。