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