算法图论

二分图判定

字数统计: 1.5k字   |   阅读时长: 7分
, ,

摘要: 本文介绍欧拉路径的判定定理、算法、代码模板和例题。

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

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

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

二分图判定

存在一个 无向图 ，图中有 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] 维护信息。

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

非二分图的判定条件：

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