如何在有向图中测试二分图
how to test for bipartite in directed graph
尽管我们可以在任何给定的无向图上使用 BFS 和 DFS（2 着色）检查图是否是二分图，但相同的实现可能不适用于有向图。
因此，为了在有向图上进行相同的测试，我正在使用我的源图 G1 构建一个新的无向图 G2，这样对于每条边 E[u -> v]，我都会在 G2 中添加一条边 [u,v]。
因此，通过应用 2 着色 BFS，我现在可以确定 G2 是否是二分的。
这同样适用于 G1，因为这两者在结构上相同。但是这种方法成本很高，因为我对图形使用了额外的 space。虽然这足以满足我现在的目的，但我想知道是否有更好的实现。
提前致谢。
你也可以执行算法在有向图上找到无向图的2-分区，你只需要稍微扭曲一下。 （顺便说一句，在下面的算法中，我假设你最终会找到一个 2 着色。如果没有，那么你将 运行 到一个已经着色的节点中，你发现你需要将它着色为另一种颜色。然后你就退出说它不是二分法。）
从任意节点开始，遍历边进行二次着色。如果您遍历了图中的每条边和每个节点，那么您就有了分区。如果不是，那么你有一个 2 色组件 and 没有边缘离开组件。选择不在组件中的任何节点并重复。如果你遇到这样一种情况，当你有一些组件都是 2 色的，并且没有任何边缘离开它们时，and 你会遇到一条起源于节点的边缘您当前正在构建的组件并进入先前组件之一的节点，然后您只需将当前组件与旧组件合并（并且可能需要翻转其中一个组件中每个节点的颜色 - 在较小的组件）。合并后继续。您可以进行合并，因为在合并时您只扫描了两个组件之间的一条边，因此翻转其中一个组件的颜色会使您处于有效状态。
时间复杂度仍然是 O(max(|N|,|E|))，您只需要为每个节点添加一个额外字段，指示该节点所在的组件。
尽管我们可以在任何给定的无向图上使用 BFS 和 DFS（2 着色）检查图是否是二分图，但相同的实现可能不适用于有向图。
因此，为了在有向图上进行相同的测试，我正在使用我的源图 G1 构建一个新的无向图 G2，这样对于每条边 E[u -> v]，我都会在 G2 中添加一条边 [u,v]。
因此，通过应用 2 着色 BFS，我现在可以确定 G2 是否是二分的。 这同样适用于 G1，因为这两者在结构上相同。但是这种方法成本很高，因为我对图形使用了额外的 space。虽然这足以满足我现在的目的，但我想知道是否有更好的实现。
提前致谢。
你也可以执行算法在有向图上找到无向图的2-分区，你只需要稍微扭曲一下。 （顺便说一句，在下面的算法中，我假设你最终会找到一个 2 着色。如果没有，那么你将 运行 到一个已经着色的节点中，你发现你需要将它着色为另一种颜色。然后你就退出说它不是二分法。）
从任意节点开始，遍历边进行二次着色。如果您遍历了图中的每条边和每个节点，那么您就有了分区。如果不是，那么你有一个 2 色组件 and 没有边缘离开组件。选择不在组件中的任何节点并重复。如果你遇到这样一种情况，当你有一些组件都是 2 色的，并且没有任何边缘离开它们时，and 你会遇到一条起源于节点的边缘您当前正在构建的组件并进入先前组件之一的节点，然后您只需将当前组件与旧组件合并（并且可能需要翻转其中一个组件中每个节点的颜色 - 在较小的组件）。合并后继续。您可以进行合并，因为在合并时您只扫描了两个组件之间的一条边，因此翻转其中一个组件的颜色会使您处于有效状态。
时间复杂度仍然是 O(max(|N|,|E|))，您只需要为每个节点添加一个额外字段，指示该节点所在的组件。