AI summary
type
status
date
slug
summary
category
tags
icon
password

二分图简介

先来看二分图的定义：
二分图的顶点集可分割为两个互不相交的子集，图中每条边依附的两个顶点都分属于这两个子集，且两个子集内的顶点不相邻。
其实图论里面很多术语的定义都比较拗口，不容易理解。我们甭看这个死板的定义了，来玩个游戏吧：
给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？
这就是图的「双色问题」，其实这个问题就等同于二分图的判定问题，如果你能够成功地将图染色，那么这幅图就是一幅二分图，反之则不是：
notion image
在具体讲解二分图判定算法之前，我们先来说说计算机大佬们闲着无聊解决双色问题的目的是什么。
首先，二分图作为一种特殊的图模型，会被很多高级图算法（比如最大流算法）用到。从简单实用的角度来看，二分图结构在某些场景可以更高效地存储数据。
比如说我们需要一种数据结构来储存电影和演员之间的关系：某一部电影肯定是由多位演员出演的，且某一位演员可能会出演多部电影。你使用什么数据结构来存储这种关系呢？
既然是存储映射关系，最简单的不就是使用 哈希表 嘛，我们可以使用一个 HashMap<String, List<String>> 来存储电影到演员列表的映射，如果给一部电影的名字，就能快速得到出演该电影的演员。
但是如果给出一个演员的名字，我们想快速得到该演员演出的所有电影，怎么办呢？这就需要「反向索引」，对之前的哈希表进行一些操作，新建另一个哈希表，把演员作为键，把电影列表作为值。
显然，如果用哈希表存储，需要两个哈希表分别存储「每个演员到电影列表」的映射和「每部电影到演员列表」的映射。但如果用「图」结构存储，将电影和参演的演员连接，很自然地就成为了一幅二分图。
每个电影节点的相邻节点就是参演该电影的所有演员，每个演员的相邻节点就是该演员参演过的所有电影，对比哈希表的存储方式更方便直观，所需的存储空间更小。
其实生活中不少实体的关系都能自然地形成二分图结构，所以在某些场景下图结构也可以作为存储键值对的数据结构（符号表）。
好了，接下来进入正题，说说如何判定一幅图是否是二分图。

二分图的判定

判定二分图的算法很简单，就是用代码解决「双色问题」。
说白了就是遍历一遍图，一边遍历一边染色，看看能不能用两种颜色给所有节点染色，且相邻节点的颜色都不相同。
既然说到遍历图，也不涉及最短路径之类的，当然是 DFS 算法和 BFS 皆可了，DFS 算法相对更常用些，所以我们先来看看如何用 DFS 算法判定双色图。
首先，基于 图结构的遍历 写出图的遍历框架：
因为图中可能存在环，所以用 visited 数组防止走回头路。
这里可以看到我习惯把 return 语句都放在函数开头，因为一般 return 语句都是 base case，集中放在一起可以让算法结构更清晰。
其实，如果你愿意，也可以把 if 判断放到其它地方，比如图遍历框架可以稍微改改：
这种写法把对 visited 的判断放到递归调用之前，和之前的写法唯一的不同就是，你需要保证调用 traverse(v) 的时候，visited[v] == false。
为什么要特别说这种写法呢？因为我们判断二分图的算法会用到这种写法。
回顾一下二分图怎么判断，其实就是让 traverse 函数一边遍历节点，一边给节点染色，尝试让每对相邻节点的颜色都不一样。
所以，判定二分图的代码逻辑可以这样写：
如果你能看懂上面这段代码，就能写出二分图判定的具体代码了，接下来看两道具体的算法题来实操一下。

785. 判断二分图

给你输入一个 邻接表 表示一幅无向图，请你判断这幅图是否是二分图。
结合之前的代码框架，我们可以额外使用一个 color 数组来记录每个节点的颜色，从而写出解法代码：
接下来看一下 BFS 算法的逻辑：
核心逻辑和刚才实现的 traverse 函数（DFS 算法）完全一样，也是根据相邻节点 v 和 w 的颜色来进行判断的。

886. 可能的二分法

给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
其实这题考察的就是二分图的判定：
如果你把每个人看做图中的节点，相互讨厌的关系看做图中的边，那么 dislikes 数组就可以构成一幅图；
又因为题目说互相讨厌的人不能放在同一组里，相当于图中的所有相邻节点都要放进两个不同的组；
那就回到了「双色问题」，如果能够用两种颜色着色所有节点，且相邻节点颜色都不同，那么你按照颜色把这些节点分成两组不就行了嘛。
所以解法就出来了，我们把 dislikes 构造成一幅图，然后执行二分图的判定算法即可：