algorithm - 广度优先搜索时间复杂度

Question

我想问，为什么BFS的时间复杂度不是O(V)而是O(E+V)？

原因是要检查的队列存储元素最多排队 V 次。所以我们在队列中最多有 V 个条目。所以入队最多出现V次，入队是bfs中出现频率最高的操作。所以顺序应该是 O(V)

标签： algorithmgraphbig-obreadth-first-search

Answer 1

扩展@beaker的评论：

您完全正确，在完整的广度优先搜索过程中，只有 O(|V|) 个总节点排队，这正是您提到的原因。但是，入队并不是在 BFS 期间执行的最频繁的操作，因此您不能从这一点开始声称运行时为 O(|V|)。

在 BFS 中，每当一个节点从队列中出列时，它的每个邻居都会被扫描以查看是否也应该将它添加到队列中。这意味着，在 BFS 的完整运行中，每条边最多被扫描一次（如果图是有向图）或最多扫描两次（如果它是无向图，则在每个端点出队时扫描一次）。总的来说，这增加了 O(|E|) 必须完成的额外工作，这既解释了其他术语的来源，也说明了为什么主要工作不纯粹是在入队和出队中。

希望这可以帮助！