💡 技术前沿
博客园精华
学习NOTE 8——二分图 - _T_M_T
博客园精华 ·
2026-09-08 17:02
· 0 浏览
AI 摘要
_T_M_T
博客园
首页
新随笔
联系
订阅
管理
学习NOTE 8——二分图
好久没写图论的学习笔记了，来写一发最近做题学的
二分图
。
是什么
二分图
就是类似于把一个图分成两半，分为左部点和右部点。听上去是“二分”，其实和二分算法没什么关系，就是一个分成两半的图。
举个例子：
就是像上图一样把一个图分成左部点和右部点两个部分。
那这是用来干什么的？
一般是在一个图上求出最大匹配数量/判断能否把点分成两个集合，且所有边都在集合之间。上面两种主要的问题一般用
匈牙利算法
和
染色法
解决。
怎么实现
上述两种算法我们分开讲。
1.匈牙利算法
要看最大匹配数量，那我们可以从一方入手，因为通常
关注公众号「网英的日常」，
第一时间获取行业资讯推送！