虽然我们可以在任何给定的无向图上使用 BFS 和 DFS(2 种着色)检查图是否是二分图，但相同的实现可能不适用于有向图。
因此，为了在有向图上进行相同的测试，我使用我的源图 G1 构建一个新的无向图 G2，这样对于每条边 E[u -> v]，我在 G2 中添加一条边 [u,v]。
因此，通过应用 2 着色 BFS，我现在可以确定 G2 是否是二分的。 这同样适用于 G1，因为两者结构相同。但这种方法成本高昂，因为要使用额外的图表空间。尽管这足以满足我现在的目的，但我想知道是否有更好的实现。
提前致谢。
最佳答案
您也可以执行该算法来在有向图上找到无向图的 2 划分，您只需要一点点改动即可。 (顺便说一句，在下面的算法中，我假设您最终会找到 2 种颜色。如果没有，那么您将遇到一个已经着色的节点，并且您发现需要将其着色为另一种颜色。然后您只需退出说它不是双向的。)
从任意节点开始，通过遍历边缘进行 2 色着色。如果您已经遍历了图中的每条边和每个节点，那么您就拥有了分区。如果不是，则您的组件是 2 色的并且没有边缘离开该组件。选择不在组件中的任何节点并重复。如果您遇到这样的情况:您有几个组件都是 2 色的，并且没有任何边离开它们，并且您会遇到源自组件中节点的边当前正在构建并进入先前组件之一中的节点，然后您只需将当前组件与旧组件合并(并且可能需要翻转其中一个组件中每个节点的颜色 - 在较小的组件中翻转它) 。合并后继续。您可以进行合并，因为在合并时您仅扫描了两个组件之间的一条边缘，因此翻转其中一个组件的颜色将使您处于有效状态。
时间复杂度仍然是 O(max(|N|,|E|))，您所需要的只是为每个节点添加一个额外字段，指示该节点位于哪个组件中。
关于algorithm - 如何测试有向图中的二部，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33857758/