算法图算法

二部图判定定理与算法

字数统计: 2.6k字   |   阅读时长: 11分
, , , ,

摘要: 本文介绍二部图判定定理与二部图判定算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 图论1-基本概念 中我了解了二部图的定义和一些性质。

本文我们以力扣第 785 题为模板题，看一下如何进行二部图判定，有 BFS、DFS、并查集三种解法。之后解决相关的题目力扣第 886 题。

二部图判定定理

定理和推论中，需要用到关于路径的一些概念：

1
2
3
4
路径相关概念：
途径 Chain/Walk  -> 闭途径      点、边均可能重复
迹 Trail         -> 闭迹 (回)   边互不相同
路 Path          -> 闭路 (圈)   点互不相同

定理（二部图的充要条件）：若 D 是强联通有向图，则 D 是二部图 $\Leftrightarrow D$ 不含有向奇回。

证明：

记 $D = (V, E, \psi_{D})$。

($\Leftarrow$) 设 $D$ 是二部划分位 $\{X, Y \}$ 的二部有向图。$D$ 中长位 $k$ 的有向回记为：

不妨设 $x_{0} \in X$，因为 $D$ 是二部图，所以：

因为 $x_{0} \in X$，所以 $X_{k-1}\in Y$

于是存在 $i$ 使得 $k-1 = 2i+1$，即 $k = 2i + 2$，因此 $C$ 是有向偶回。

($\Rightarrow$) 由于 $D$ 不含有向奇回，因此 $D$ 肯定没有自环。考虑 $v(D) \geq 2$ 的情况。

任取 $u \in V(D)$，构造以下两个 $V(D)$ 的子集：

一方面 $u \in X$，另一方面由于 $D$ 是强连通的，因此 $Y \neq \varnothing$，$\{X, Y\}$ 是 $V(D)$ 的划分。

下面证明 $Y$ 的导出子图 $D[Y]$ 中没有边，也就是 $E(D[Y]) = 0$。

若 $|Y| = 1$，则 $E(D(Y)) = 0$ 成立。下面考虑 $|Y| \geq 2$ 的情况。取 $y,z\in Y, y\neq z$。由于 $D$ 是强连通的，可以定义以下几条路：

  • $P_{1}$：最短 $(u, y)$ 路；
  • $Q_{1}$：最短 $(u, z)$ 路；
  • $P_{2}$：最短 $(y, u)$ 路；
  • $Q_{2}$：最短 $(z, u)$ 路。

由 $Y$ 的定义，$P_{1}$ 和 $Q_{1}$ 的长度均为奇数，由于 $D$ 不含奇回，而 $P_{1} \oplus P_{2}$ 和 $Q_{1} \oplus Q_{2}$ 均含有 $D$ 中的有向回。所以 $P2$ 和 $Q_{2}$ 的长度也是奇数。

因此，若存在 $e \in E(D)$ 使得 $\psi_{D}(e) = (z, y)$，则 $P_{2} \oplus Q_{1} \oplus e$ 是 $D$ 中的有向奇回，矛盾。

若存在 $e \in E(D)$ 使得 $\psi_{D}(e) = (y, z)$，则 $Q_{2} \oplus P_{1} \oplus e$ 是 $D$ 中的有向奇回，矛盾。因此 $E(D[Y]) = 0$，也就是 $Y$ 中任意两点不相邻。

类似地可以证明 $X$ 中任意两顶点不相邻，因此 $D$ 是二部图。 $\Box$

推论1：若 D 是强联通有向图，则 D 是二部图 $\Leftrightarrow D$ 不含有向奇圈。

证明：

($\Leftarrow$) 由二部图判定定理，$D$ 不含有向奇回，因此 $D$ 不含有向奇圈。

($\Rightarrow$) $D$ 不含有向奇圈，下面证明 $D$ 不含有向奇回。假设 $D$ 中含有向奇回，设有向奇回为 $C$。由于 $D$ 中不含有向奇圈，因此 $C$ 不是有向圈。

$C$ 可以表示成 $k$ 条不相交有向圈 $C_{1}, C_{2}, \cdots, C_{k}$ 的并 $C = C_{1}\oplus C_{2}\oplus \cdots \oplus C_{k}$，由于 $C$ 的长度为奇数：

因此 $\epsilon(C_{i}), i=1,2,\cdots,k$ 中必有一个为奇数，矛盾。因此 $D$ 中不含有向圈，由二部图判定定理，$D$ 为二部图。

推论2：若 G 是无向图，则 G 是二部图 $\Leftrightarrow D$ 不含奇圈。

证明：

$G$ 是二部图 $\Leftrightarrow$ $G$ 的每个连通分量都是 2 部图。不妨设 $G$ 是连通的。

考虑 $G$ 的对称有向图 $D$。$G$ 是连通的 2 部图 $\Leftrightarrow$ $D$ 是强连通的 2 部图。

另一方面，$G$ 中不含奇圈 $\Leftrightarrow$ $D$ 中不含有向奇圈。

由推论1，G 是二部图 $\Leftrightarrow D$ 不含奇圈。

二部图判定算法

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

  • 不存在自环（graph[u] 不包含 u）。
  • 不存在平行边（graph[u] 不包含重复值）。
  • 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
  • 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

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

如果图是二分图，返回 true ；否则，返回 false 。

提示：

1
2
3
4
5
6
7
graph.length == n
1 <= n <= 100
0 <= graph[u].length < n
0 <= graph[u][i] <= n - 1
graph[u] 不会包含 u
graph[u] 的所有值 互不相同
如果 graph[u] 包含 v，那么 graph[v] 也会包含 u

示例 1：
输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

示例 2：
输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

算法1：BFS + 染色

在 BFS 过程中，用距离数组 d[u] 维护信息，其中 0 标记未访问过的顶点，1 和 -1 是顶点的染色，分别代表二部划分的两个集合。

1
2
3
d[u] = 0 : 未访问过的点(灰色点)
d[u] = 1 : 黑色点
d[u] = -1 : 白色点

每次从当前顶点 u 走到下一顶点 v 时，令 d[v] = -d[u] 原因在于如果是二部图，相邻顶点属于不同的二部划分，因此相邻顶点的颜色不一样，

在这种情况下，如果 v 是此前访问过的顶点，说明此时遇到了一个圈，按照二部图判定定理，如果这个圈的长度是奇数则图肯定不是二部图。按照前面对顶点染色的定义，以及在搜索过程中相邻顶点设置颜色不同，圈的长度为奇数等价于 d[u] = d[v]，

因此非二分图的判定条件如下：

1
2
if(d[u] == d[v])
    return false;

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        if(graph.empty()) return false;
        int n = graph.size();
        if(n == 1) return true;

        int st;
        vector<int> d(n, 0);

        for(int i = 0; i < n; ++i)
        {
            if(d[i] != 0) continue;
            st = i;
            d[st] = 1;
            if(!bfs(graph, st, d))
                return false;
        }
        return true;
    }

private:
    bool bfs(const vector<vector<int>>& g, int st, vector<int>& d)
    {
        queue<int> q;
        q.push(st);
        while(!q.empty())
        {
            int u = q.front(); // 当前点
            q.pop();
            for(int v: g[u])
            {
                if(d[v] != 0)
                {
                    if(d[u] == d[v])
                        return false;
                    else
                        continue;
                }
                d[v] = -d[u];
                q.push(v);
            }
        }
        return true;
    }

};

算法2：DFS + 染色

染色和判定逻辑均与 BFS + 染色的算法相同。

将 bool bfs(const vector<vector<int>>& g, int st, vector<int>& d); 改为 bool dfs(const vector<vector<int>>& g, int u, vector<int>& d);，接口也一样。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool dfs(const vector<vector<int>>& g, int u, vector<int>& d)
{
    for(int v: g[u])
    {
        if(d[v] != 0)
        {
            if(d[v] == d[u])
                return false;
            continue;
        }
        d[v] = -d[u];
        if(!dfs(g, v, d))
            return false;
    }
    return true;
}

算法3：并查集

如果是二部图的话，那么图中每个顶点的所有邻接点都应该属于同一集合，且不与顶点处于同一集合。

这种对于集合的维护也可以用并查集。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class UnionFindSet {
public:
    UnionFindSet(int n)
    {
        _father = vector<int>(n, -1);
        _rank = vector<int>(n, 0);
        for(int i = 0; i < n; ++i)
            _father[i] = i;
    }

    ~UnionFindSet(){}

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    void merge(int x, int y)
    {
        x = _find(x);
        y = _find(y);
        if(x == y) return;

        // 此时 x, y 是所在树的根
        if(_rank[x] < _rank[y])
            _father[x] = y;
        else
        {
            _father[y] = x;
            if(_rank[x] == _rank[y])
                ++_rank[x];
        }
    }

private:
    vector<int> _father;
    vector<int> _rank;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        else
            return _father[x] = _find(_father[x]); // 路径压缩
    }
};

class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        UnionFindSet unionfindset(n);
        for(int u = 0; u < n; ++u)
        {
            if(graph.empty())
                continue;
            int m = graph[u].size();
            int v0 = graph[u][0];
            for(int i = 1; i < m; ++i)
            {
                int v = graph[u][i];
                if(unionfindset.same(u, v))
                    return false;
                unionfindset.merge(v0, v);
            }
        }
        return true;
    }
};

题目

给定一组 n 人（编号为 1, 2, …, n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。

给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

提示：

1
2
3
4
5
6
1 <= n <= 2000
0 <= dislikes.length <= 1e4
dislikes[i].length == 2
1 <= dislikes[i][j] <= n
ai < bi
dislikes 中每一组都 不同

示例 1：
输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]

示例 2：
输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false

示例 3：
输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false

代码：建图+二部图判定

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> g(N);
        for(const vector<int>& edge: dislikes)
        {
            g[edge[0] - 1].push_back(edge[1] - 1);
            g[edge[1] - 1].push_back(edge[0] - 1);
        }
        return isBipartite(g);
    }
};
Share