为什么DFS和时间复杂度BFS O（V + E）为什么DFS和时间复杂度BFS O（V + E）(W

The basic algorithm for 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

So I would think the time complexity would be:

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

where v is vertex 1 to n

Firstly, is what I've said correct? Secondly, how is this O(N + E), and intuition as to why would be really nice. Thanks

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)时间
• 每个顶点被标记两次
  • 一次是未知
  • 曾经为已访问
• 每个边缘被标记两次
  • 一次是未知
  • 作为一次发现或BACK
• 方法incidentEdges为每个顶点调用一次
• DFS在运行O(n + m)时提供的图由邻接列表结构表示
• 回想一下， Σv deg(v) = 2m

BFS（分析）：

• 设置/获取一个顶点/边标签花费O（1）时间
• 每个顶点被标记两次
  • 一次是未知
  • 曾经为已访问
• 每个边缘被标记两次
  • 一次是未知
  • 作为一次发现或CROSS
• 每个顶点中插入一次顺序Li
• 方法incidentEdges为每个顶点调用一次
• BFS在运行O(n + m)时提供的图由邻接列表结构表示
• 回想一下， Σv deg(v) = 2m

Answer 3:

非常简化没有太多的形式：每边被认为是准确的两倍，并且每一个节点被处理恰好一次，所以复杂性必须是边缘的数目的常数倍以及顶点的数量。

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. 一个用于在所有入射边缘环 - > 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> 

[O（1）+ O（E）]

文章来源: Why is the time complexity of both DFS and BFS O( V + E )