为什么深度优先搜索和广度优先搜索的时间复杂度都是 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)，有直观的解释会很好。谢谢。

- ordinary

---

我发现这个解释非常清晰易懂。 - Kaveh

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)。

- Mihai Maruseac

---

但是每个顶点都必须从队列中提取，这需要log（|Q|）时间。那么这部分怎么办？ - Yola

log(|Q|) < log(N) < N，因此您可以安全地忽略渐进式中的这个项。 - Mihai Maruseac

如果在邻接表中，每个顶点都连接到所有其他顶点，那么复杂度将等同于O(V+E)=O(V+V^2)=O(V^2)。其中E=V^2，因为最多的边数为V^2。 - Max

根据您的回答，复杂度不会变成O(V+2E)吗？因为每条边都可能与另一条边有公共边？ - karansky

可以忽略常数项。 - Mihai Maruseac

但是每个顶点都必须从队列中提取，这是log（|Q|）吗？绝对不是！这是一个链表而不是堆队列。 - Tomas G.

Answer 2

DFS(分析):

• 设置/获取顶点/边的标签需要O(1)时间
• 每个顶点被标记两次
  • 一次为UNEXPLORED
  • 一次为VISITED
• 每条边被标记两次
  • 一次为UNEXPLORED
  • 一次为DISCOVERY或BACK
• 对于每个顶点，方法incidentEdges会被调用一次
• 如果采用邻接表结构表示图，则DFS运行时间为O(n + m)
• 记得Σv deg(v) = 2m

BFS(分析):

• 设置/获取顶点/边的标签需要O(1)时间
• 每个顶点被标记两次
  • 一次为UNEXPLORED
  • 一次为VISITED
• 每条边被标记两次
  • 一次为UNEXPLORED
  • 一次为DISCOVERY或CROSS
• 每个顶点被插入到序列Li中一次
• 对于每个顶点，方法incidentEdges会被调用一次
• 如果采用邻接表结构表示图，则BFS运行时间为O(n + m)
• 记得Σv deg(v) = 2m

- TheNewOne

---

谢谢您的编辑，我在这里还是新手，所以仍在努力适应编辑界面 :) - TheNewOne

感谢您明确指出图形要用邻接表结构表示，这让我明白为什么深度优先搜索是O(n+m)，如果没有这个提示我会认为它是O(n+2m)，因为回溯时每条边都会被遍历两次。 - mib1413456

Answer 3

非常简化而不太正式：每条边恰好被考虑两次，每个节点恰好被处理一次，因此复杂度必须是边数和顶点数的常数倍。

- Neetesh Dadwariya

---

虽然这就是谷歌存在的原因，但比起数学符号而言，理解起来要简单得多。 - mLstudent33

为什么每条边都被认为是正好两次？ - amy

每个顶点最多只被访问一次，因为只有第一次到达它时距离才为零，所以每个顶点最多只入队一次。由于我们只在从一个顶点访问时检查与其相邻的边，因此每条边最多被检查两次，分别是对应它所关联的两个顶点。[参见来源] (https://www.khanacademy.org/computing/computer-science/algorithms/breadth-first-search/a/analysis-of-breadth-first-search#:~:text=Each%20vertex%20is%20visited%20at,the%20vertices%20it's%20incident%20on) - Neetesh Dadwariya

Answer 4

一个直观的解释是通过分析单个循环来实现的：

1. 访问一个顶点 -> O(1) 2. 对所有与给定顶点v相关的边进行循环 -> O(e)，其中e是与给定顶点v相关的边的数量。

因此，单个循环的总时间为O(1)+O(e)。现在将其累加到每个顶点上，因为每个顶点只被访问一次。这就得到了结果。

For every V
=> 
    
    O(1)
    +

    O(e)

=> O(V) + O(E)

由于我们只访问每个节点一次。

- Ultrablendz

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 之间的差异则不重要。

- Dhruvam Gupta

---

@Am_I_Helpful 有人在上面询问大O符号中的2E问题...这就是为什么2不被考虑在时间复杂度中的原因。 - Dhruvam Gupta

@Am_I_Helpful，只需查看我的答案上面的帖子......那里的用户Kehe CAI写道：“我认为每个边缘都被考虑了两次，每个节点都被访问了一次，因此总时间复杂度应该是O(2E+V)。”所以我回答了相应的问题......明白了吗！！！ - Dhruvam Gupta

我撤销了我的反对票，仅仅是因为你编辑了你的回答。 - Am_I_Helpful

Answer 6

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

- Kehe CAI

---

我也有同样的感觉。有人可以对此进行进一步解释吗？ - Chaitanya

大O分析忽略常数。O(2E+V)等同于O(E+V)。 - Hemm

在大 O 分析中，通常会去掉常数和非主导部分。 - Bowen

Answer 7

简短而简单的解释：

在最坏的情况下，您需要访问所有顶点和边，因此最坏情况下的时间复杂度为O（V + E）。

- CodeYogi

Answer 8

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

- Himanshu

Answer 9

这是O(V+E)的，因为对于V中的每个v的访问都必须访问E中的每个e，其中|e| <= V-1。由于对V中的v进行了V次访问，因此时间复杂度为O(V)。现在您必须添加V * |e| = E => O(E)。因此总时间复杂度为O(V + E)。

- awgtek