2

我知道 BFS 在图遍历中的时间复杂度是O( V + E )因为在最坏的情况下将探索每个顶点和每条边。

那么，确切的时间复杂度是v+2E？？

每个顶点被探索一次+每个相邻顶点

a中所有顶点的度数之和graph= No of edges*2= 2E

因此时间复杂度是n+2E..我正确吗？

4

2 回答 2

2

对于随机图，时间复杂度为O(V+E)：广度优先搜索

如链接中所述，根据您的图的拓扑，O(E)可能会有所不同O(V)（如果您的图是非循环的）到O(V^2)（如果所有顶点都相互连接）。

因此，时间复杂度O(V + V) = O(V)会O(V + V^2) = O(V^2)根据图形的拓扑而有所不同。

此外，since |V| <= 2 |E|，thenO(3E) = O(E)也是正确的，但界限更宽松。

于 2013-09-04T13:44:31.887 回答
0

假设

假设 G 是连通的且无向的。如果它没有连接，那么您可以将以下想法独立应用于 G 的每个连接组件。此外，假设 G 表示为邻接列表，并且对于每个顶点 v，我们可以确定 v 是否在 O(1) 时间内被访问，例如使用查找表。

分析

如果您想计算 BFS 中的确切步数，您可以观察到：

  1. 由于 G 是连通的，BFS 将恰好访问每个顶点一次，所以我们计算 |V| 节点访问。请注意，在一次访问中，您可能会执行更多操作，而不是仅标记当前访问的顶点，而不是计算边上的循环。

  2. 对于我们要计算的每个顶点 v，BFS 在该顶点检查了多少条边。

您必须遍历 v 的所有边才能执行 BFS。如果你跳过一个边缘，那么很容易表明 BFS 是不正确的。所以每条边都要检查两次。

这里可能会出现一个问题。有人可能会问，是否需要检查顶点 v 中的边 (p, v)，其中 p 是 v 在已经构建的 BFS 树中的父节点，即我们直接从 p 来到 v。当然你不必考虑这条边，但决定跳过这条边也至少要花费一个额外的操作：

for (v, u) in v.edges:
    if u == p: # p is the parent of v in already constructed tree
        continue
    if not visited[u]:
        BFS(u, parent=v)

它检查的边数与下面的代码相同，但复杂度更高，因为除了一条边外，我们运行两条 if 语句而不是一条。

for (v, u) in v.edges:
    if not visited[u]: # if p is the parent of v, then p is already visited
        BFS(u, parent=v)

结论

你甚至可以开发一种不同的方法来跳过边 (v, p)，但它总是需要至少一个操作，所以这是一种浪费的努力。

于 2013-09-05T00:29:01.583 回答