为什么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)时间
• 每个顶点都标记两次
  • 曾经作为UNEXPLORED
  • 一旦被邀请
• 每条边都标记两次
  • 曾经作为UNEXPLORED
  • 曾经发现或回复
• 方法incidentEdges为每个顶点调用一次
• O(n + m)如果图形由邻接列表结构表示,则DFS 及时运行
• 回想起那个 ?v deg(v) = 2m

BFS(分析):

• 设置/获取顶点/边缘标签需要O(1)时间
• 每个顶点都标记两次
  • 曾经作为UNEXPLORED
  • 一旦被邀请
• 每条边都标记两次
  • 曾经作为UNEXPLORED
  • 曾经作为DISCOVERY或CROSS
• 每个顶点一次插入序列中 Li
• 方法incidentEdges为每个顶点调用一次
• O(n + m)如果图形由邻接列表结构表示,则BFS 及时运行
• 回想起那个 ?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

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

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 6

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