二分图判定 :: labuladong的算法小抄

[labuladong]

文章链接点这里：二分图判定

评论礼仪 见这里，违者直接拉黑。

[jswxwxf]

js 785. 判断二分图 DFS 解法

var isBipartite = function(graph) {
  const n = graph.length;
  // 记录图是否符合二分图性质
  let valid = true;
  // 记录图中节点是否被访问（着色）过
  const visited = {};
  // 记录图中节点的颜色，false 和 true 代表两种不同颜色
  const colors = new Array(n).fill(false);
  // 因为图不一定是联通的，可能存在多个子图
  // 所以要把每个节点都作为起点进行一次遍历
  // 如果发现任何一个子图不是二分图，整幅图都不算二分图
  for (let v = 0; v < n; v++) {
    if (visited[v]) continue;
    traverse(v);
  }
  return valid;

  // DFS 遍历框架
  function traverse(v) {
    // 如果已经确定不是二分图了，就不用浪费时间再递归遍历了
    if (!valid) return;

    visited[v] = true;
    for (const n of graph[v]) {
      // 相邻节点被访问过
      // 比较两个节点的颜色是否相同
      // 比如相同，则不是二分图
      if (visited[n]) {
        if (colors[n] === colors[v]) {
          valid = false;
          return;
        }
        continue;
      }
      // 相邻节点没有被访问过
      // 那么涂色
      colors[n] = !colors[v];
      // 继续遍历
      traverse(n);
    }
  }

};

js 785. 判断二分图 BFS 解法

var isBipartite = function(graph) {
  const n = graph.length;
  // 记录图是否符合二分图性质
  let valid = true;
  // 记录图中节点是否被访问（着色）过
  const visited = {};
  // 记录图中节点的颜色，false 和 true 代表两种不同颜色
  const colors = new Array(n).fill(false);
  // 因为图不一定是联通的，可能存在多个子图
  // 所以要把每个节点都作为起点进行一次遍历
  // 如果发现任何一个子图不是二分图，整幅图都不算二分图
  for (let v = 0; v < n; v++) {
    if (visited[v]) continue;
    traverse(v);
  }
  return valid;

  // BFS 遍历框架
  function traverse(start) {
    const q = [start];
    visited[start] = true;
    while (q.length && valid) {
      const v = q.shift();
      // 从节点 v 向所有相邻节点扩散
      for (const n of graph[v]) {
        // 相邻节点被访问过
        // 比较两个节点的颜色是否相同
        // 比如相同，则不是二分图
        if (visited[n]) {
          if (colors[n] === colors[v]) {
            valid = false;
            return;
          }
          continue;
        }
        // 相邻节点没有被访问过
        // 那么涂色
        colors[n] = !colors[v];
        visited[n] = true;
        q.push(n);
      }
    }
  }

};

js 886. 可能的二分法

let valid = true;
  const colors = new Array(n + 1).fill(false);
  const visited = [];
  // 转化成邻接表表示图结构
  const graph = buildGraph();
  // 图节点编号从 1 开始
  for (let v = 1; v <= n; v++) {
    if (visited[v]) continue;
    traverse(v);
  }
  return valid;

  // 建图
  function buildGraph() {
    // 图节点编号为 1...n
    const graph = new Array(n + 1).fill(0).map(
      () => []
    );
    for (const [v, n] of dislikes) {
      // 「无向图」相当于「双向图」
      graph[v].push(n);
      graph[n].push(v);
    }
    return graph;
  }

  function traverse(v) {
    if (!valid) return;
    visited[v] = true;
    for (const n of graph[v]) {
      if (visited[n]) {
        // 相邻着色相同，说明不喜欢的两个人分到同一组了
        if (colors[n] === colors[v]) {
          valid = false;
          return;
        }
        continue;
      }
      colors[n] = !colors[v];
      traverse(n);
    }
  }

[omgwtfholyshit]

210「 课程表 II」的BFS解法则使用入度作为算法入口

 Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indgree[i] == 0) {
            // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            q.offer(i);
        }
    }

当解答 785「 判断二分图」的时候，发现入度全部不为0，根本无法进入BFS循环。
看了题解才知道，对于不一定连通的图，BFS的循环方式如下：

 for (int v = 0; v < n; v++) {
        if (!visited[v]) {
            bfs(graph, v);
        }
    }

那么我可不可以这么理解：
入度出度的适用范围是：1. 有向图 并且 2.图是连通的
循环调用BFS的适用范围是：1.无向图 或者 2.图未必连通

[labuladong]

@omgwtfholyshit 你可以理解为，indegree 数组只适用于拓扑排序的场景，其他场景的 BFS/DFS 遍历都是配合 visited 数组进行的。

[LebronHarden1]

明白了,如果不能通过下标找到下一个节点就得建图,或者说让每个数组下标代表一个人,下标所在元素(一个链表)代表这个人能走向的目的地.所以有时候根据二维数组的定义就是天然的邻接表,有些题得自己建

[Yuguo-Wang]

785的dfs和bfs框架，为什么bfs里if not visited[w]以后需要标记该节点为已访问而dfs不需要呢，一直没有想清楚。。

[labuladong]

@Yuguo-Wang DFS 是在递归的前序遍历位置标记该节点，和 BFS 入队前标记该节点本质上是一样的

[fmxs]

C++

#include <vector>
using namespace std;
class Solution{
public:
    vector<bool> color;   // 给结点染色
    vector<bool> visited; // 保存访问过的结点
    bool isBi = true;     // 是否符合二分图
    bool isBipartite(vector<vector<int>> &graph){
        visited.resize(graph.size());
        color.resize(graph.size());
        for (int i = 0; i < graph.size(); i++)// 图可能并不连通
            if (!visited[i] && isBi)  traverse(graph, i);
        return isBi;
    }

    void traverse(vector<vector<int>> &graph, int v){
        visited[v] = true;
        for (int n : graph[v]) {// 遍历顶点v的所有邻居顶点
            if (visited[n] == false) {
                color[n] = !color[v];// 没访问过的顶点，染成反色
                traverse(graph, n);
            }
            else{
                if (color[n] == color[v])   isBi = false;// 两个相邻顶点同色，不符合二分图
            }
        }
    }
};

有帮助的话请点个赞再走~

[labuladong]

👍

[chengrenfeng]

c++ bfs

class Solution {
public:
    bool ok {true};
    vector<bool> visited;
    vector<bool> color;
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        visited.resize(n);
        color.resize(n);
        for(int i = 0; i < n; i++) {
            if(!visited[i]&&ok){
                bfs(graph,i);
            }
        }
        return ok;
    }

    void bfs(vector<vector<int>>& graph,int &s){
        queue<int> q;
        q.emplace(s);
        while(!q.empty() && ok){
            int v = q.front();
            q.pop();  
            visited[v] = true;      
            for(const auto &w : graph[v]){
                if(!visited[w]){
                    color[w] = !color[v];
                    q.emplace(w);
                }else if(color[w] == color[v]){
                    ok = false;
                    return;
                }
            }
        }
    }
};

[MSTE-sysu]

785 Python3
DFS

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        #DFS
        self.isBp = True
        self.visited = set()
        self.colormap = {}
        for i in range(len(graph)):
            #已遍历过的连接子图跳过
            if i not in self.visited:
                self.colormap[i] = 0
                self.traverse(i,graph)
        return self.isBp
    
    def traverse(self,node,graph):
        if not self.isBp:
            return
        self.visited.add(node)
        for nextnode in graph[node]:
            if nextnode not in self.visited:
                self.colormap[nextnode] = (self.colormap[node] + 1) % 2
                self.traverse(nextnode,graph)
            else:
                if self.colormap[nextnode] == self.colormap[node]:
                    self.isBp = False
                    return
        return

BFS

class Solution:
    #BFS
    def isBipartite(self, graph: List[List[int]]) -> bool:
        isBp = True
        colormap = {}
        visited = set()
        for i in range(len(graph)):
            #已遍历过的连接子图跳过
            if i not in visited:
                queue = deque()
                queue.append(i)
                visited.add(i)
                colormap[i] = 0
                while queue and isBp:
                    curNode = queue.popleft()
                    for nextNode in graph[curNode]:
                        if nextNode not in visited:
                            colormap[nextNode] = (colormap[curNode] + 1) % 2
                            queue.append(nextNode)
                            visited.add(nextNode)
                        else:
                            if colormap[nextNode] == colormap[curNode]:
                                isBp = False
                                break
        return isBp

[LeeHaruYa]

滴滴滴打卡

[davidelena]

多谢东哥的分享很有用

[yonggui-yan]

滴滴打卡

[liuyunqing0]

学到了！

[MzxlM]

lt 886 bfs

class Solution {
    boolean ok = true;
    boolean[] visited;
    boolean[] color;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        visited = new boolean[n+1];
        color = new boolean[n+1];
        
        List<Integer>[] graph = buildGraph(n, dislikes);
        for (int i = 1; i < n+1; i++) {
            if(!visited[i]) traverse(graph, i);
        }
        
        return ok;
    }
    
    List<Integer>[] buildGraph(int n, int[][] graph) {
        List<Integer>[] res = new LinkedList[n+1];
        for(int i = 1; i <= n; i++) {
            res[i] = new LinkedList<>();
        }
        
        for (int[] edge: graph) {
            int v = edge[0];
            int w = edge[1];
            res[v].add(w);
            res[w].add(v);
        }
        
        return res;
        
    }
    
    void traverse(List<Integer>[] graph, int v) {
        if(!ok) return;
        
        visited[v] = true;
        
        Queue<Integer> q = new LinkedList<>();
        
        q.offer(v);
        while(!q.isEmpty()) {
            int t = q.poll();
            for(int w : graph[t]) {
                if(!visited[w]) {
                    color[w] = !color[t];
                    visited[w] = true;
                    q.add(w);
                } else {
                    if(color[w] == color[t]) {
                        ok = false;
                        return;
                    }
                }
            }
        }
        
    }
}

[GoingMyWay]

C++ 实现检测二分图

class Solution {
public:
    bool ok = true;
    vector<bool> colors;
    vector<bool> visited;
    queue<int> q;
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        colors = vector<bool>(n, false);
        visited = vector<bool>(n, false);
        for (int i = 0; i < n; i ++) {
            if (!visited[i])
                // dfs(i, graph);
                bfs(i, graph);
        }
        return ok;
    }

    void bfs(int node, vector<vector<int>>& graph) {
        visited[node] = true;
        q.push(node);
        
        while (q.size() && ok) {
            int v = q.front(); q.pop();
            for (int w : graph[v]) {
                if (!visited[w]) {
                    colors[w] = !colors[v];
                    visited[w] = true;
                    q.push(w);
                } else {
                    if (colors[w] == colors[v]) {
                        ok = false;
                        return;
                    }
                }
            }
        }
    }

    void dfs(int v, vector<vector<int>>& graph) {
        if (!ok) return;

        visited[v] = true;
        for (int w: graph[v]) {
            if (!visited[w]) {
                colors[w] = !colors[v];
                dfs(w, graph);
            } else {
                if (colors[w] == colors[v]) ok = false;
            }

        }
    }
};

[GoingMyWay]

C++ 886题的实现

class Solution {
public:
    bool ok = true;
    vector<bool> colors;
    vector<bool> visited;
    queue<int> q;

    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph = buildGraph(n, dislikes);
        return isBipartite(graph);
    }

    vector<vector<int>> buildGraph(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> graph(n);
        for (auto vs: dislikes) {
            graph[vs[0]-1].push_back(vs[1]-1);
            graph[vs[1]-1].push_back(vs[0]-1);
        }
        return graph;
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        colors = vector<bool>(n, false);
        visited = vector<bool>(n, false);
        for (int i = 0; i < n; i ++) {
            if (!visited[i])
                // dfs(i, graph);
                bfs(i, graph);
        }
        return ok;
    }

    void bfs(int node, vector<vector<int>>& graph) {
        visited[node] = true;
        q.push(node);
        
        while (q.size() && ok) {
            int v = q.front(); q.pop();
            for (int w : graph[v]) {
                if (!visited[w]) {
                    colors[w] = !colors[v];
                    visited[w] = true;
                    q.push(w);
                } else {
                    if (colors[w] == colors[v]) {
                        ok = false;
                        return;
                    }
                }
            }
        }
    }

    void dfs(int v, vector<vector<int>>& graph) {
        if (!ok) return;

        visited[v] = true;
        for (int w: graph[v]) {
            if (!visited[w]) {
                colors[w] = !colors[v];
                dfs(w, graph);
            } else {
                if (colors[w] == colors[v]) ok = false;
            }

        }
    }

};

[yusun97]

为什么这里不需要onPath呢

[flyingkkk]

请问东哥，886题，为什么在构建无向图时，写成“graph[w].add(v); graph[v].add(w);“时无法通过n=2000时的用例？谢谢

[FRAOTIAC]

C++

class Solution {
public:
    bool ok = true;
    vector<bool> color;
    vector<bool> visited;
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        color.resize(n, false);
        visited.resize(n, false);

        for (int v = 0; v < n; v ++) {
            if(!visited[v]) {
                bfs(graph, v);
            }
        }
        return ok;
    }

    void bfs(vector<vector<int>> &graph, int v) {
        if (!ok) {
            return;
        }
        queue<int> q;
        q.push(v);

        while (q.size() && ok) {
            int start = q.front();
            q.pop();
            visited[start] = true;
            for (auto node: graph[start]) {
                if(!visited[node]) {
                    q.push(node);
                    color[node] = !color[start];
                } else {
                    if (color[node] == color[start]) {
                        ok = false;
                        return;
                    }
                }
            }
        }
    }
};

[Hanmu-Zuo]

有一点想不通，为什么886这题一定要构建无向图才能通过，构造有向图会挂。我想不通这个corner case，我觉得有向图也可以解决这个问题呀

[labuladong]

无向图其实就是双向图。讨厌关系是双向的，所以当然要构建无向图。

[Infinite-Unexpired-Love]

我也想不通

[realRuiGuo]

有相同的疑问

[gaosh96]

看到了一道应该是判断二分图的变种，不知道该怎么做了，不是相邻颜色必须不同，而是只要不是红色就行

给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？
输入描述：
第一行输入M(图中节点数) N(边数)
后续N行格式为：V1 V2表示一个V1到V2的边。
数据范围：1 <= M <= 15,0 <= N <= M * 3，不能保证所有节点都是连通的。
输出描述：
输出一个数字表示染色方案的个数。

示例1：
输入：
4 4
1 2
2 4
3 4
1 3
输出：
7

[lixryjz]

这个和上一个拓朴排序的回溯可以一样么，就是在遍历图的时候

[mrc321]

感觉还是尽量少写这种将答案作为全局变量的代码，破坏了方法的封装性。

[LittleBox17]

不是很理解用dislikes建图，dislikes和graph不是同一个东西吗？

[forexgg]

我有点不太明白，那个染色的二分图，左边的那个两个蓝的连起来不就不是二分图了？右边的那个两个蓝的不连，不就是二分图了？是不是 不是只是染色的结果。因为还得看定义的边？

[LittleBox17]

您好，已收到。

[Infinite-Unexpired-Love]

东哥，为什么判断二分图需要使用无向图啊，使用有向图不可以吗

[zjfjack]

我写的也是有向图，就是出错了，我思考了一下感觉主要还是代码好写以及容易理解

假设有四个人 1 -> 2 -> 3 <- 4 其实可以分组成 (1, 3) (2, 4)
有向图过程:

1. 默认给1白色 => 遍历到2，给2黑色 => 遍历到3，给3白色
2. 由于2,3已经遍历过，直接跳过
3. 默认给4白色 => 遍历到3发现3也是白色，完蛋，return false

如果我们默认给初始颜色的时候还要去检查相邻节点的NODE颜色情况应该就会弄得很复杂，但是无向图就没这个问题，因为只要有连接就必定会遍历到。

无向图的过程:

1. 默认给1白色 => 遍历到2，给2黑色 => 遍历到3，给3白色 => 遍历到4，给4黑色
2. 跳过2, 3, 4 结束 return true

[LittleBox17]

您好，已收到。

[Link-GZJ]

大佬🐂皮

[LittleBox17]

您好，已收到。