为什么DFS和BFS O（V + E）的时间复杂性

BFS的基本algorithm：

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)次
• 每个顶点被标记两次
  • 一度被视为不了了之
  • 曾经被访问过
• 每条边都被标记了两次
  • 一度被视为不了了之
  • 一次作为发现或后退
• 方法incidentEdges每个顶点被调用一次
• 如果graphics由邻接表结构表示，则DFS在O(n + m)时间内运行
• 回想一下Σv deg(v) = 2m

BFS（分析）：

• 设置/获取顶点/边缘标签需要O（1）次
• 每个顶点被标记两次
  • 一度被视为不了了之
  • 曾经被访问过
• 每条边都被标记了两次
  • 一度被视为未被开发
  • 一旦发现或交叉
• 每个顶点被插入一个序列Li
• 方法incidentEdges每个顶点被调用一次
• BFS在O(n + m)时间运行，只要graphics由邻接表结构表示
• 回想一下Σv deg(v) = 2m

Answer 3

非常简化，没有太多forms化：每条边都被认为是两次，每个节点只处理一次，所以复杂度必须是边数和顶点数的常数倍。

Answer 4

时间复杂度是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 5

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

Answer 6

简短但简单的解释：

我最糟糕的情况是你需要访问所有的顶点和边缘，因此最坏情况下的时间复杂度是O（V + E）

Answer 7

直观的解释是通过简单地分析一个单一的循环：

1. 访问一个顶点 – > O（1）
2. 在所有入射边上的for循环 – > O（e）其中e是入射到给定顶点v上的边的数量。

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

Sigma_i

 p { height: 50px; line-height: 50px; } span { position: relative; font-size: 2.5em; display: inline-block; line-height: .7em; vertical-align: middle; } span:before { font-size: 12px; display: block; position absolute; left: 0; top: 0; content: "V"; width: 22px; text-align: center; } span:after { font-size: 12px; display: block; position absolute; left: 0; bottom: 0; content: "k = 1"; width: 27px; text-align: center; } 

 <p> <span>&Sigma;</span> O(1) + O(e) => <span>&Sigma;</span> O(1) + <span>&Sigma;</span> O(e) => O(V) + O(E) </p>