如何通过划分颜色的二分图？

Question

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

V = {A，B，C，d}，点击 E = {（A，B），（A，d），（C，d）}

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

Answer 1

您第一猜测是正确的 - 遍历图形和备用

该算法应该是简单的。我会保持节点的两个队列参观，每种颜色一个。弹出交替节点离开队列，标记颜色，和任何未访问过的相邻节点推入队列为相反的颜色。终止时访问的节点的数目+两个队列的长度=图中的节点的数目。

Answer 2

遍历图形和替代，如果它不succeded这意味着您的图不是二分

Answer 3

如果您是确保该图是biparte，那么你可以指定颜色交替它们用于遍历每个顶点，因为它认为：

  

一个图是二分当且仅当它是2-着色。

Answer 4

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

如果二分图连接，其bipartition可以通过从任何任意选择的顶点v的距离的奇偶定义：一个子集由顶点的在连到v距离和所述另一个子集在奇数距离由顶点的到v。

因此，可以有效地测试一个图是否是二分通过使用该奇偶校验技术来顶点分配给两个子集U和V，分别在图的每个连接组件内，然后检查每个边缘，以验证它有端点分配给不同的子集。

Answer 5

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

我刚刚标志着一个顶点为左partity，然后递归标志着它的邻国如右图partity，递归地纪念他们的邻居左partity ...如果你找到正确标记节点上，停止该分支的递归。如果您发现uncorrectly明显的节点，图是不是二分。

也许这是可以做到简单，但在过去的几个月里我有一些硬的Prolog - 哈斯克尔编码天，也许这影响了我的大脑，现在我看到的一切:-D递归

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。