168

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)，以及为什么会非常好的直觉。谢谢

4

9 回答 9

313

你的总和

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

于 2012-07-13T10:29:30.750 回答
44

DFS（分析）：

  • 设置/获取顶点/边标签需要O(1)时间
  • 每个顶点被标记两次
    • 曾经作为 UNEXPLORED
    • 曾经访问过
  • 每条边被标记两次
    • 曾经作为 UNEXPLORED
    • 一次作为 DISCOVERY 或 BACK
  • 对每个顶点调用一次方法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
于 2012-07-13T10:28:47.380 回答
29

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

于 2014-12-17T06:04:35.303 回答
18

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

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

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

For every V
=> 

    O(1)
    +

    O(e)

=> O(V) + O(E)
于 2017-08-07T09:27:56.877 回答
14

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

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

因为 n^2 和 n 之间的差异很重要，但 n 和 2n 之间的差异不重要。

于 2015-09-10T15:39:03.750 回答
5

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

于 2015-07-21T08:23:36.493 回答
3

简短而简单的解释：

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

于 2016-07-27T04:17:21.767 回答
0

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

于 2021-11-30T16:39:47.367 回答
-1

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

于 2020-09-26T06:53:32.817 回答