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