algorithm - 如何在有向图中测试二分图

Question

虽然我们可以在任何给定的无向图上使用 BFS 和 DFS(2 着色)检查图是否是二分图，但相同的实现可能不适用于有向图。

因此，为了在有向图上进行相同的测试，我正在使用我的源图 G1 构建一个新的无向图 G2，这样对于每个边 E[u -> v]，我都会在 G2 中添加一个边 [u,v]。

因此，通过应用 2 着色 BFS，我现在可以确定 G2 是否是二分的。这同样适用于 G1，因为这两者在结构上相同。但是这种方法成本很高，因为我要为图形使用额外的空间。虽然这足以满足我现在的目的，但我想知道是否有更好的实现。

提前致谢。

Answer 1

您也可以执行该算法以在有向图上找到无向图的 2-partition，您只需要稍微改变一下。 (顺便说一句，在下面的算法中，我假设你最终会找到一个二次着色。如果没有，那么你会遇到一个已经着色的节点，你发现你需要将它着色为另一种颜色。然后你就退出说它不是二分法。)

从任意节点开始，通过遍历边进行二次着色。如果您遍历了图中的每条边和每个节点，那么您就有了分区。如果不是，那么您的组件是 2 色的并且没有离开组件的边缘。选择不在组件中的任何节点并重复。如果您遇到这样一种情况，当您有几个组件都是 2 色的，并且没有任何边缘离开它们时，并且您会遇到一条起源于组件中的节点的边缘当前正在构建并进入先前组件之一的节点然后您只需将当前组件与旧组件合并(并且可能需要翻转其中一个组件中每个节点的颜色 - 在较小的组件中翻转它) .合并后继续。您可以进行合并，因为在合并时您只扫描了两个组件之间的一条边，因此翻转其中一个组件的颜色会使您处于有效状态。

时间复杂度仍然是 O(max(|N|,|E|))，您只需要为每个节点添加一个额外字段，指示该节点位于哪个组件中。