为什么 DFS 和 BFS O (V + E)都具有时间复杂性

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)，和直觉为什么会真的很好。谢谢

225870 次浏览
小开

外勤部(分析) :

  • 设置/获取顶点/边标签需要 O(1)时间
  • 每个顶点都标记了两次
    • 曾经是未开发的
    • 有人来过一次
  • 每个边都标记了两次
    • 曾经是未开发的
    • 一次作为发现或回来
  • 对每个顶点调用一次
  • 如果图是由邻接列表结构表示的，那么 DFS 在 O(n + m)时间内运行
  • 回想一下那个 Σv deg(v) = 2m

BFS (分析) :

  • 设置/获取顶点/边标签需要 O (1)时间
  • 每个顶点都标记了两次
    • 曾经是未开发的
    • 有人来过一次
  • 每个边都标记了两次
    • 曾经是未开发的
    • 一次作为发现或交叉
  • 每个顶点插入一次序列 Li
  • 对每个顶点调用一次
  • BFS 在 O(n + m)时间内运行，只要图是由邻接列表结构表示的
  • 回想一下那个 Σv deg(v) = 2m
小开
最佳答案

你的总数

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

小开

非常简化，没有太多的形式: 每个边都被精确地考虑两次，每个节点被精确地处理一次，所以复杂度必须是边数和顶点数的常数倍。

小开

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

小开

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

因此，O (2E + V)被写成 O (E + V)

因为 n ^ 2和 n 物质之间的差异，而不是 n 和2n 之间的差异。

小开

简短而简单的解释:

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

小开

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

  1. 访问顶点-> O (1)
  2. A 在所有入射边上的 for 循环-> O (e) ，其中 e 是在给定顶点 v 上入射的若干边。

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

For every V
=>


O(1)
+


O(e)


=> O(V) + O(E)
小开

它是 O (V + E) ，因为每次访问 V 的 v 都必须访问 E 的每个 e，其中 | e | < = V-1。既然 V 对 V 的 v 有访问，那么这就是 O (V)。现在必须加上 V * | e | = E = > O (E)。所以总时间复杂度是 O (V + E)。

小开

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


提交答案