二分图判定

判断无向图是否二分图,并在是时给出二染色;BFS/DFS 染色,冲突等价于奇环。

标签 图论 / 二分图 / 染色 / BFS / DFS

问题形式

给定无向图 𝐺=(𝑉,𝐸),判断它是否为 二分图;若是,给出一组二染色或两部划分。

算法

对每个未染色的连通分量任选起点,染为颜色 0,用 BFS 或 DFS 把相邻点染成相反颜色。

若遇到一条边两端已经同色,则不存在合法二染色,输出否;全部分量处理完且没有冲突,输出是。

正确性

出现同色边时,沿 BFS/DFS 树上的两条路径和这条边会形成一个奇环,所以图不是二分图。

反过来,若染色过程没有冲突,则每条边都连接不同颜色,两个颜色类就是合法的两部。

复杂度

时间 𝑂(𝑛+𝑚),空间 𝑂(𝑛+𝑚)。

源码位置