time-complexity - dfs 还是 bfs 更适合在有向图上测试二部？

Question

如果我想检查两个测试色度/如果 有向 图是二部图，那么我使用广度优先搜索还是深度优先搜索有关系吗？就时间复杂度而言，一种更有效吗？

Answer 1

图是有向图还是无向图实际上根本无关紧要；无论边是哪个方向，它两端的两个节点必须有不同的颜色。因此，对于无向图，答案完全相同。

我还将假设图形是连接的，以便每个节点都可以从 node_0 到达；这不会真正产生影响，因为无论哪种方式，您都只会在每个连接的组件上独立运行算法。但它确实简化了分析。

DFS 或 BFS 如下所示。唯一的区别是 to_visit.get_one() 和 to_visit.put_one() 的行为； DFS 使用堆栈(后进先出)，而 BFS 使用队列(先进先出)。

def is_bipartite(node_0):
    to_visit = [node_0]
    colors = { node_0: 'RED' }

    while to_visit:
        node = to_visit.get_one()
        color1 = colors[node]
        color2 = 'BLUE' if color1 == 'RED' else 'RED'

        for neighbour in node.neighbours:
            if neighbour not in colors:
                colors[neighbour] = color2
                to_visit.put_one(neighbour)
            elif colors[neighbour] == color1:
                return False

    return True

考虑到算法的时间复杂性，在任何一种情况下:

每个节点最多插入一次 to_visit ，因为只有当它不在 colors 中时才会插入，但是我们在插入时将其添加到 colors 中。

我们最多迭代 node.neighbours 一次，因为 1.

因此，两种算法在最坏情况下的迭代次数相同； O(E) 其中 E 是图中的边数。