如何通过颜色对二分图进行划分？

Question

例如，假设我有一个图G =（V，E），其中

V = {A，B，C，D} E = {(A，B)，（A，D），（C，D）}

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

- Jason Baker

Answer 1

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

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

- Pete Kirkham

---

或者简单地编写一个递归深度优先搜索函数，传递一个颜色参数。 - Mehrdad Afshari

大多数足够有趣的图形会在递归DFS上引起SO。 - Pete Kirkham

这只是一个广度优先搜索算法。没有必要保留两个队列；一个单独的队列就足够了（因为你在遍历过程中标记节点的颜色）。 - ShreevatsaR

这取决于您是标记节点本身还是将节点分成两个集合而不改变它们；后者使用两个队列更有效率。 - Pete Kirkham

Answer 2

来自维基百科 (http://en.wikipedia.org/wiki/Bipartite_graph)

如果一个二分图是连通的，它的二分法可以通过从任意选定的顶点v到其他顶点的距离的奇偶性来定义：一个子集包含到v的偶数距离的顶点，另一个子集包含到v的奇数距离的顶点。

因此，我们可以使用这种奇偶性技巧在每个连通分量内分别将顶点分配给两个子集U和V，并检查每条边，以验证其端点是否被分配给不同的子集，从而有效地测试一个图是否为二分图。

- peter.murray.rust

---

我已经知道这个图是二分图了。我想把它分成不相交的集合。 - Jason Baker

这个答案中的“test”是一个构造性过程；当测试成功时，您将拥有两个不相交的部分。 - ShreevatsaR

@Jason，正如@ShreevatsaR所说，运行测试将必然导致根据两个集合标记顶点。 - peter.murray.rust

Answer 3

遍历图并交替，如果不成功则意味着您的图不是二分图。

- rachvela

Answer 4

如果你确定这个图是二分图，那么你可以为遍历每个顶点交替地分配颜色，因为它满足以下条件：

当且仅当一个图是二分图时，它才能被涂成两种颜色。

- MicSim

Answer 5

我在我的图形绘制工具中实现了它，你可以看到我的JavaScript代码。

我只是将第一个顶点标记为左部分，然后递归地将其邻居标记为右部分，递归地将它们的邻居标记为左部分...如果你找到正确标记的节点，请停止这个分支的递归。如果你发现未正确标记的节点，则图不是二分图。

也许可以更简单地完成，但在过去几个月中，我经历了一些艰难的Prolog-Haskell编码日子，也许它影响了我的大脑，现在我在任何事情中都看到递归 :-D

- Ivan Kuckir

Answer 6

如果有人感兴趣，这是我想出来的代码：

def dfs(root, colorings):
    to_visit1 = deque()
    to_visit2 = deque()
    to_visit1.append(root)
    while len(to_visit1) != 0 or len(to_visit2) != 0:
        dfs_color(to_visit1, to_visit2, True, colorings)
        dfs_color(to_visit2, to_visit1, False, colorings)

def dfs_color(queue, opposite_queue, color, colorings):
    while len(queue) != 0:
    v = queue.pop()
    if v in adjacency_list:
        colorings[v] = color
        neighbors = adjacency_list[v]
        del adjacency_list[v]
        for neighbor in neighbors:
        opposite_queue.append(neighbor)

诚然，这不是我最好的代码。我使用True/False作为颜色，因为当我使用递归时，只需说not color就很容易。当然，我不得不改变它，因为在更大的图形上我会爆栈。此外，为了给予应有的信用，这段代码基于维基百科DFS的代码。

虽然正如所指出的那样，我认为这可能只是一个伪装的BFS。

- Jason Baker