algorithm - 如何按颜色划分二分图？

Question

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

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

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

Answer 1

您的第一个猜测是正确的 - 遍历图并交替。

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