时间戳

首页 > 解决方案 > 为什么是 BFS O(n+m)？

algorithm - 为什么是 BFS O(n+m)？

问题描述

在此处输入图像描述

在最坏的情况下，第一个 while 循环需要访问所有节点。这是n。对于每个访问节点，它需要检查所有相邻节点/边。我认为这应该是 O(n*maximum deg(u))。为什么在谷歌中找到的所有答案都说你只需要访问每个节点和边一次，所以它是 O(n+m)？访问相邻节点/边将访问重复/访问节点。如果他们被访问，您只是不将它们添加到列表中。我认为这仍然有一个运行时。例如：a->b->c 我们从a开始，检查相邻节点b，将c添加到列表中。然后去b。然后从b去检查a和c，a被访问了，所以把c加入到列表中，然后去c。从 b 探索时，我们需要 O(2)/O(deg(b)。

标签： algorithmgraphruntimebig-obreadth-first-search

解决方案

这样想：

  1. 拥有 2 个嵌套循环并不一定意味着它们的复杂性会成倍增加
  2. 外循环遍历所有节点，所以这很O(n)复杂。没有节点被多次添加到队列中。
  3. 对于给定的节点，我们遍历它的所有邻居。对于任何节点，邻居数=节点的度数。由于我们有效地遍历每个节点的所有邻居一次，因此总复杂度为O(sum of all node's degree). 由于图中所有度数的总和是边数，复杂度 = = 。2*mmO(2*m)O(m)

总复杂度 =O(n+m)

推荐阅读