01二分图
# 01 二分图
二分图算法也称为染色法,是一种广度优先搜索。如果可以用两种颜色对图中的节点进行着色,并且保证相邻的节点颜色不同,那么图为二分。
二分图定义:如果能将一个图的节点集合分割成两个独立的子集 A 和 B ,并使图中的每一条边的两个节点一个来自 A 集合,一个来自 B 集合,就将这个图称为 二分图 。
# 785 判断二分图 (opens new window)
给定一个图,判断其是否可以二分
输入是邻接链表表示的图(如位置 0 的邻接链表为 [1,3],表示 0 与 1、0 与 3 相连);输出是一个布尔值,表示图是否二分。
输入:graph = [[1,3],[0,2],[1,3],[0,2]] 输出:true 解释:可以将节点分成两组: {0, 2} 和 {1, 3} 。
解析:
利用队列和广度优先搜索,我们可以对未染色的节点进行染色,并且检查是否有颜色相同的相邻节点存在。如果遍历完所有节点没有颜色相同的相邻节点,则该图为二分图;否则就不是二分图。在遍历过程中,我们用 0 表示未检查的节点,用 1 和 2 表示两种不同的颜色。
我们任选一个节点开始,将其染成 1 色,并从该节点开始对整个无向图进行遍历;
在遍历的过程中,如果我们通过节点 u 遍历到了节点 v,那么会有两种情况:如果 v 未被染色,那么我们将其染成与 u 不同的颜色,并对 v 直接相连的节点进行遍历;如果 v 已经被染色,并且颜色与 u 相同,那么说明给定的无向图不是二分图,可以直接退出并返回 False。
当遍历完成时,说明给定的无向图是二分图,返回 True。
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
if(graph.empty()){
return false;
}
vector<int> color(graph.size(),0);
queue<int> q;
for(int i=0;i<graph.size();++i){
if(!color[i]){
q.push(i);
color[i] = 1;
}
while(!q.empty()){
int node = q.front();
q.pop();
// 对 v 直接相连的节点进行遍历
for(const auto& j: graph[node]){
if(!color[j]){
q.push(j);
color[j] = color[node] == 2?1:2;
}else if(color[j] == color[node]){
return false;
}
}
}
}
return true;
}
};
上次更新: 2023/11/19, 12:55:48