二分图判定
判断无向图是否二分图,并在是时给出二染色;BFS/DFS 染色,冲突等价于奇环。标签 图论 / 二分图 / 染色 / BFS / DFS
问题形式
给定无向图 ,判断它是否为 二分图;若是,给出一组二染色或两部划分。
算法
对每个未染色的连通分量任选起点,染为颜色 ,用 BFS 或 DFS 把相邻点染成相反颜色。
若遇到一条边两端已经同色,则不存在合法二染色,输出否;全部分量处理完且没有冲突,输出是。
正确性
出现同色边时,沿 BFS/DFS 树上的两条路径和这条边会形成一个奇环,所以图不是二分图。
反过来,若染色过程没有冲突,则每条边都连接不同颜色,两个颜色类就是合法的两部。
复杂度
时间 ,空间 。