如何在有向图中测试二分法 [英] how to test for bipartite in directed graph

问题描述

尽管我们可以在任何给定的无向图上使用BFS和DFS（2色）检查图是否为二部图，但对于有向图来说，相同的实现可能不起作用。

Although we can check a if a graph is bipartite using BFS and DFS (2 coloring ) on any given undirected graph, Same implementation may not work for the directed graph.

因此，要在有向图上进行相同的测试，请使用我的源图G1构建一个新的无向图G2，以便为每个边缘E [u-> v]在G2中添加一个边缘[u，v]。

So for testing same on directed graph , Am building a new undirected graph G2 using my source graph G1, such that for every edge E[u -> v] am adding an edge [u,v] in G2.

因此，通过应用2色BFS，我现在可以确定G2是否是二分的。
和G1相同，因为这两个在结构上相同。但是，这种方法的成本很高，因为要为图形使用额外的空间。尽管到目前为止，这已经满足了我的目的，但我想知道是否还有更好的实现方法。

So by applying a 2 coloring BFS I can now find if G2 is bipartite or not. and same applies for the G1 since these two are structurally same. But this method is costly as am using extra space for graph. Though this will suffice my purpose as of now, I'd like know if there any better implementations for the same.

预先感谢。

推荐答案

您可以执行以下算法：在有向图上也找到无向图的2分区，只需要稍作改动即可。 （顺便说一句，在下面的算法中，我假设您最终将找到2色。如果没有，那么您将遇到一个已经着色的节点，您需要将其着色为另一种颜色。然后退出

You can execute the algorithm to find the 2-partition of an undirected graph on a directed graph as well, you just need a little twist. (BTW, in the algorithm below I assume that you will eventually find a 2-coloring. If not, then you will run into a node that is already colored and you find you need to color it to the other color. Then you just exit saying it's not bipartite.)

从任何节点开始，并通过遍历边缘进行2色处理。如果遍历了图形中的每个边和每个节点，则将拥有分区。如果不是，则您的组件是的2色，并且没有任何边缘。选择不在组件中的任何节点，然后重复。如果遇到一种情况，即您的组件全部都是2色的，并且没有任何边缘留下，和会遇到一条边缘，该边缘起源于组件中的某个节点当前正在构建并进入先前组件之一的节点中，然后您只需将当前组件与较旧的组件合并即可（可能需要翻转其中一个组件中每个节点的颜色-将其翻转到较小的组件中） 。合并后继续。您可以进行合并，因为在合并时您仅扫描了两个组件之间的一条边缘，因此翻转其中一个组件的颜色会使您处于有效状态。

Start from any node and do the 2-coloring by traversing the edges. If you have traversed every edge and every node in the graph then you have your partition. If not, then you have a component that is 2-colored and there are no edges leaving the component. Pick any node not in the component and repeat. If you get into a situation when you have a few components that are all 2-colored, and there are no edges leaving any of them, and you encounter an edge that originates in a node in the component you are currently building and goes into a node in one of the previous components then you just merge the current component with the older one (and possibly need to flip the color of every node in one of the components -- flip it in the smaller component). After merging just continue. You can do the merge, because at the time of the merge you have scanned only one edge between the two components, so flipping the coloring of one of the components leaves you in a valid state.

时间复杂度仍为O（max（| N |，| E |）），并且您需要为每个节点添加一个额外字段，指示该节点位于哪个组件中。

The time complexity is still O(max(|N|,|E|)), and all you need is an extra field for every node indicating which component that node is in.

这篇关于如何在有向图中测试二分法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！