如何按颜色分割二分图？

Question

例如,假设我有一个图G =(V,E)其中

V = {A,B,C,D}
E = {(A,B),(A,D),(C,D)}

该图是二分的,因此可以分成两个不相交的集合{A,C}和{B,D}.我的第一个猜测是我可以简单地走图形并为每个顶点指定交替的颜色.是这种情况,还是比这更复杂/更简单？有没有任何已知的算法？

Answer 1

你的第一个猜测是正确的 - 遍历图表并交替.

算法应该很简单.我要保留两个节点队列,每种颜色一个.从队列中弹出节点交替,标记其颜色,并将任何未访问的相邻节点推入队列中以获得相反的颜色.当访问节点的数量+两个队列的长度=图中的节点数时终止.