为什么DFS和BFS的时间复杂度都是O(V + E)

Question

BFS的基本算法：

set start vertex to visited

load it into queue

while queue not empty

   for each edge incident to vertex

        if its not visited

            load into queue

            mark vertex

所以我认为时间复杂度是：

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges) 

其中

v

是顶点

1

到

n

首先我说的对吗？其次，这是如何

O(N + E)

，以及关于为什么的直觉会非常好。谢谢

Answer 1

您的金额

v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)

可以重写为

(v1 + v2 + ... + vn) + [(incident_edges v1) + (incident_edges v2) + ... + (incident_edges vn)]

第一组是

O(N)

，而另一组是

O(E)

。

Answer 2

DFS（分析）：

• 设置/获取顶点/边标签需要

  O(1)

  时间
• 每个顶点被标记两次
  • 曾经未被探索过
  • 访问过一次
• 每条边都标记两次
  • 曾经未被探索过
  • 一旦发现或返回
• 每个顶点调用一次 eventEdges 方法
• DFS 在

  O(n + m)

  时间内运行，前提是图由邻接表结构表示
• 回想一下

  Σv deg(v) = 2m

BFS（分析）：

• 设置/获取顶点/边标签需要 O(1) 时间
• 每个顶点被标记两次
  • 曾经未被探索过
  • 访问过一次
• 每条边都标记两次
  • 曾经未被探索过
  • 曾经作为DISCOVERY或CROSS
• 每个顶点在序列中插入一次

  Li

• 每个顶点调用一次 eventEdges 方法
• BFS 在

  O(n + m)

  时间内运行，前提是图由邻接列表结构表示
• 回想一下

  Σv deg(v) = 2m

Answer 3

非常简化，没有太多形式：每条边都被考虑两次，每个节点只被处理一次，因此复杂度必须是边数和顶点数的常量倍数。

Answer 4

对此的直观解释是简单地分析单个循环：

1. 访问一个顶点 -> O(1)
2. 所有入射边上的 for 循环 -> O(e)，其中 e 是入射到给定顶点 v 上的边数。

所以单个循环的总时间是 O(1)+O(e)。现在，当每个顶点被访问一次时，对每个顶点求和。这给出

For every V
=> 
    
    O(1)
    +

    O(e)

=> O(V) + O(E)

因为我们只访问每个节点一次。

Answer 5

时间复杂度是

O(E+V)

而不是

O(2E+V)

，因为如果时间复杂度是 n^2+2n+7 那么它会写成 O(n^2)。

因此，O(2E+V) 写为 O(E+V)

因为 n^2 和 n 之间的差异很重要，但 n 和 2n 之间的差异不重要。

Answer 6

我认为每条边都被考虑了两次，每个节点都被访问过一次，所以总时间复杂度应该是 O(2E+V)。

Answer 7

简短但简单的解释：

最坏的情况是你需要访问所有的顶点和边 最坏情况下的时间复杂度是 O(V+E)

Answer 8

在 Bfs 中，每个相邻顶点都会插入队列一次。这是通过查看顶点的边缘来完成的。每个访问过的顶点都被标记，因此不能再次访问：每个顶点仅访问一次，并且检查每个顶点的所有边。所以BFS的复杂度是V+E。 在DFS中，每个节点维护一个包含其所有相邻边的列表，然后，对于每个节点，您需要通过在线性时间内遍历其邻接列表一次来发现其所有邻居。对于有向图，所有节点的邻接表大小之和为E（边总数）。所以，DFS 的复杂度是 O(V + E)。

Answer 9

它的复杂度为 O(V+E)，因为每次访问 V 的 v 都必须访问 E 的每个 e，其中 |e| <= V-1. Since there are V visits to v of V then that is O(V). Now you have to add V * |e| = E => O(E)。所以总时间复杂度是 O(V + E)。