原创数据结构图论算法约 3530 字大约 12 分钟
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 785. Is Graph Bipartite? | 785. 判断二分图 | 🟠 |
| 886. Possible Bipartition | 886. 可能的二分法 | 🟠 |
| - | 剑指 Offer II 106. 二分图 | 🟠 |
Tip
本文有视频版：二分图判定算法及应用。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
我之前写了好几篇图论相关的文章：
今天继续来讲一个经典图论算法：二分图判定。
二分图简介
在讲二分图的判定算法之前，我们先来看下百度百科对「二分图」的定义：
二分图的顶点集可分割为两个互不相交的子集，图中每条边依附的两个顶点都分属于这两个子集，且两个子集内的顶点不相邻。
其实图论里面很多术语的定义都比较拗口，不容易理解。我们甭看这个死板的定义了，来玩个游戏吧：
给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？
这就是图的「双色问题」，其实这个问题就等同于二分图的判定问题，如果你能够成功地将图染色，那么这幅图就是一幅二分图，反之则不是：
在具体讲解二分图判定算法之前，我们先来说说计算机大佬们闲着无聊解决双色问题的目的是什么。