LeetCode刷题笔记图二分图

编程入门行业动态更新时间:2024-10-25 05:22:35

二分图简介

二分图算法也称为染色法，是一种广度优先搜索。如果可以用两种颜色对图中的节点进行着色，并且保证相邻的节点颜色不同，那么图为二分。

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

785 判断二分图

给定一个图，判断其是否可以二分

输入是邻接链表表示的图（如位置 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;}
};