二分图判断（染色问题）

Posted on | In | |

题目描述

785. Is Graph Bipartite?

Given a graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

即判断给定的图是否是二分图：

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

算法分析

二分图的判断可以看作染色问题。对于图中的每一个顶点S，与它直接相邻的任一顶点N，其颜色必然与S不同，则这样的图是一个二分图。

最常用也最简单的方法就是遍历（DFS或BFS）整张图，用两种不同的颜色A和B，对每个顶点染色。选定一个顶点S开始，对其进行染色，再访问它的邻居顶点N。若：

  • N还未被染色，即对它染色与S不同的颜色，并继续访问S的邻居顶点。
  • N已被染色，且其颜色与S相同，则该图不是一个二分图。
  • N已被染色，但其颜色与S不同，则继续查看和访问其它邻居节点。

访问了所有的顶点后（即完成对所有顶点的染色），该图就是一个二分图。

代码实现

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
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        vector<int> color(graph.size(), 0);
        while (true) {
            bool all_visited = true;
            queue<int> que;
            int src;
            for (int i = 0; i < color.size(); i++)
                if (color[i] == 0) {
                    src = i;
                    que.push(src);
                    color[src] = 1;
                    all_visited = false;
                    break;
                }
            if (all_visited)
                break;

            while (!que.empty()) {
                int front = que.front();
                que.pop();
                for (int i = 0; i < graph[front].size(); i++) {
                    if (color[graph[front][i]] == 0) {
                        color[graph[front][i]] = 0 - color[front];
                        que.push(graph[front][i]);
                    }
                    else if (color[graph[front][i]] == color[front]) {
                        return false;
                    }
                    else {
                        continue;
                    }
                }
            }
        }
        return true;
    }
};

需要注意的是，题目输入的图不一定是一个连通图，因此，使用DFS或BFS遍历时要注意判断是否已经访问了所有的顶点。

本文为博主原创文章，转载请注明出处。