二分图

发表于 | 分类于 | |
字数统计: 723 | 阅读时长 ≈ 3

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

说人话就是同一条边的两个顶点一定要是不一样颜色的图。

判断二分图的常见方法是染色法： 开始对任意一未染色的顶点染色，之后判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色， 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断，bfs和dfs可以搞定！

785. 判断二分图

在这道题目中，我们不需要创建图了，图已经创建好了。如果没有创建好的话，我们需要创建一个无向的图

  • 我们要对每一个点都初始遍历，因为给出的可能不是一个图，而是一个图集
  • 创建一个visited，如果这个点被访问过，那么我们就不需要处理他了。
  • 然后我们去开始遍历
  • 如果点的子节点被遍历过，那么说明它已经被染色过了，我们就要判断两者的颜色是否一致，如果一致，说明不是二分图
  • 如果点的子节点没有被遍历过，那么我们就需要将其赋予相反的颜色，然后继续递归处理。
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
class Solution {
public:
    void tranverse(int index, vector<vector<int>>& graph, vector<bool>& visited, vector<bool>& colors) {
        if (!isBipart) {
            return;
        }
        visited[index] = true;
        for (auto item : graph[index]) {
            if (visited[item]) {
                if (colors[item] == colors[index]) {
                    isBipart = false;
                    return;
                }
            } else {
                colors[item] = !colors[index];
                tranverse(item, graph, visited, colors);
            }
        }
    }
    bool isBipartite(vector<vector<int>>& graph) {
        int numPoints = graph.size();
        vector<bool> visited(numPoints, false);
        vector<bool> colors(numPoints, false);
        for (int i = 0; i < numPoints; i++) {
            if (!visited[i]) {
                tranverse(i, graph, visited, colors);
            }
        }
        return isBipart;
    }
private:
    bool isBipart = true;
};

上面的方法是用dfs来解决处理的，对于图遍历，还可以用bfs来解决。

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
class Solution {
public:
    void tranverse(int index, vector<vector<int>>& graph, vector<bool>& visited, vector<bool>& colors) {
        queue<int> q;
        q.push(index);
        visited[index] = true;
        while (!q.empty() && isBipary) {
            auto curr = q.front();
            q.pop();
            for (auto item : graph[curr]) {
                if (visited[item]) {
                    if (colors[item] == colors[curr]) {
                        isBipary = false;
                        break;
                    }
                } else {
                    colors[item] = !colors[curr];
                    q.push(item);
                    visited[item] = true;
                }
            }
        }
    }
    bool isBipartite(vector<vector<int>>& graph) {
        int nums = graph.size();
        vector<bool> visited(nums, false);
        vector<bool> colors(nums, false);
        for (int i = 0; i < nums; i++) {
            if (!isBipary) {
                return isBipary;
            }
            if (!visited[i]) {
                tranverse(i, graph, visited, colors);
            }
        }
        return isBipary;
    }
private:
    bool isBipary = true;
};

显示 Gitment 评论