二分图

目录

1. 定义

二分图的顶点集可分割为两个互不相交的子集

  • 每条边依附的两个顶点都分别属于这两个子集
  • 两个子集内的顶点不相邻

图片&文件

1.1. 通俗的定义：双色问题

给你一幅图，如果你能用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，那么这幅图就是一幅二分图

图片&文件

2. 使用场景：如何表达电影与演员的关系

  • 两个哈希表：
    • ① 演员 → 电影列表
    • ② 电影 → 演员列表
  • 图
    • 图片&文件
    • 优势：
      • 更方便直观
      • 所需的存储空间更小

3. 判定二分图 → 题目