判断二分图

二 题目

给定一个无向图 graph，当这个图为二分图时返回 true。

如果我们能将一个图的节点集合分割成两个独立的子集 A 和 B，
并使图中的每一条边的两个节点一个来自 A 集合，
一个来自 B 集合，
我们就将这个图称为二分图。

graph 将会以邻接表方式给出，
graph[i] 表示图中与节点i相连的所有节点。

每个节点都是一个在 0 到 graph.length-1 之间的整数。

这图中没有自环和平行边： graph[i] 中不存在 i，
并且 graph[i] 中没有重复的值。


示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

注意:
graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-graph-bipartite
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function(graph) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
const isBipartite = (graph) => {
  const visited = new Array(graph.length); // 0为未染色，1为蓝色，-1为黄色
  for (let i = 0; i < graph.length; i++) { // 遍历每个顶点
    if (visited[i]) continue;              // 已经染了色的，跳过
    const queue = [i];           // 队列初始化推入顶点 i
    visited[i] = 1;              // 染为蓝色
    while (queue.length) {       // 遍历顶点 i 所有相邻的顶点
      const cur = queue.shift();           // 考察出列顶点
      const curColor = visited[cur];       // 出列顶点的颜色
      const neighborColor = -curColor;     // 它的相邻顶点应该有的颜色
      for (let i = 0; i < graph[cur].length; i++) {      // 给他们都上色
        const neighbor = graph[cur][i];
        if (visited[neighbor] == undefined) {            // 还没上色
          visited[neighbor] = neighborColor;             // 上色
          queue.push(neighbor);                          // 并推入队列
        } else if (visited[neighbor] != neighborColor) { // 染了，但不是对的颜色
          return false;
        }
      }
    }
  }
  return true; // 遍历完所有顶点，没有发现哪里不对
};

console.log(isBipartite(
  [[4,1],[0,2],[1,3],[2,4],[3,0]]
)); // false

console.log(isBipartite(
  [
    [1,2,3], 
    [0,2],
    [0,1,3], 
    [0,2]
  ]
)); // false

console.log(isBipartite(
  [
    [1,3], 
    [0,2],
    [1,3], 
    [0,2]
  ]
)); // true

四 统计分析

解法	执行用时 / 击败率	内存消耗 / 击败率
解法 1	240 ms / 100.00%	41.8 MB / 100.00%

五 套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。