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

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

1. 每个节点最多插入to_visit一次，因为只有当它不在colors中时才会插入，但当我们插入它时，我们会将它添加到colors中
2. 我们在node.neighbours上最多迭代一次，因为1

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