5

例如，假设我有一个图 G = (V, E) 其中

V = {A, B, C, D}
E = {(A, B), (A,D), (C, D)}

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

4

6 回答 6

5

您的第一个猜测是正确的 - 遍历图形并交替。

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

于 2009-10-31T18:26:45.827 回答
2

来自维基百科（http://en.wikipedia.org/wiki/Bipartite_graph）

如果一个二分图是连通的，它的二分可以由任意选择的顶点 v 的距离的奇偶性定义：一个子集由到 v 的偶数距离的顶点组成，另一个子集由到 v 的奇数距离的顶点组成。

因此，人们可以通过使用这种奇偶校验技术将顶点分配给两个子集 U 和 V 来有效地测试图是否是二分的，分别在图的每个连通分量内，然后检查每条边以验证它是否具有分配给不同的端点子集。

于 2009-10-31T18:33:06.383 回答
2

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

于 2009-10-31T18:57:43.837 回答
1

如果您确定该图是双向的，那么您可以只分配颜色交替它们以遍历每个顶点，因为它认为：

一个图是二分的当且仅当它是 2-colorable 的。

于 2009-10-31T18:30:42.113 回答
1

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

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

也许它可以做得更简单，但在过去的几个月里，我经历了一些艰难的 Prolog - Haskell 编码日子，也许它影响了我的大脑，现在我看到一切都在递归:-D

于 2011-10-04T11:08:54.567 回答
0

以防万一有人好奇，这是我想出的代码：

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。

于 2009-11-01T13:24:00.387 回答