41

为什么 BFS 和 DFS 的运行时间是 O(V+E),尤其是当有一个节点有一个有向边到一个可以从顶点到达的节点时,就像下面这个网站的例子一样

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

4

5 回答 5

47

E 是图中所有边的集合,如 G={V,E}。所以,|E| 是图中所有边的计数。

仅此一项就足以让您相信整体复杂性不可能是 |V| 次|E|,因为我们没有迭代图中每个顶点的所有边。

在邻接表表示中,对于每个顶点 v,我们只遍历与其相邻的那些节点。

|V| |V|+|E| 的因子 似乎来自完成的队列操作的数量。

请注意,算法的复杂性取决于所使用的数据结构。实际上,我们正在访问图表示中存在的每条信息,这就是为什么对于图的矩阵表示,复杂度变为 V 平方。

引用科门的话,

“入队和出队的操作需要 O(1) 时间,因此用于队列操作的总时间是 O(V)。因为每个顶点的邻接表只有在顶点出队时才被扫描,所以每个邻接表在最多一次。由于所有邻接表的长度之和为 Θ(E),因此扫描邻接表的总时间为 O(E)。初始化的开销为 O(V),因此总运行时间BFS 为 O( V + E)。"

于 2012-03-04T10:23:23.140 回答
24

这个问题花了我 4 个小时的时间,但最后,我想我有一个简单的方法来获取图片,一开始我很想说 O ( V * E )。

总结您在 Cormen 中找到的算法,这与http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm上的算法相同,您有这样的东西:

for (vi in V)
{
   Some O(1) instructions
   for ( e in Adj(vi) ) {
      Some O(1) instructions
   }
}

问题是这里执行了多少条指令?这将是 Sigma-Sum (Adj(vi)),该值的上限为 2|E|。

一开始,我们会自动考虑将内循环和外循环的迭代次数相乘,但在这种情况下,内循环上的总迭代次数是外迭代器的函数,因此无法进行乘法运算。

于 2012-06-16T10:51:35.620 回答
11

您最多访问每个边缘两次。有 E 边。所以会有2*E的边访问操作。加上那些没有边的节点,或者换句话说,度数为 0。最多可以有 V 个这样的节点。所以复杂度变成了,O(2*E + V) = O(E + V)

于 2015-08-02T15:06:38.227 回答
7

当您将图形视为表示为相邻列表的数据结构时,就会变得很清楚

在此处输入图像描述

您会看到顶点:A、B、C、D、E 和每个顶点/节点的相邻顶点作为这些顶点的列表。如果是循环图,您必须“查看”所有框以检查它是否已被“访问”,或者如果它是树状图,则只需遍历所有子项

于 2019-08-02T22:23:32.790 回答
1

你迭代 |V| 节点,至多 |V| 次。因为我们有 |E| 的上限 图中的总边,我们最多检查 |E| 边缘。不同的顶点会有不同数量的相邻节点,所以我们不能只乘 |V|*|E| (这意味着对于每个顶点,我们遍历 |E| 边,这是不正确的,|E| 是所有节点上边的总数),而是我们检查 V 个节点,并且我们检查总共 E边缘。最后,我们有 O(|V|+|E|)

对于 DFS,它是类似的,我们遍历所有顶点邻接列表,如果它没有被访问,则调用 DFS(v),这意味着我们会产生 |V| 时间步长,加上访问相邻节点所花费的时间(本质上,这些形成一条边,我们总共有 |E| 条边,因此,O(V+E) 时间。

    private static void visitUsingDFS(Node startNode) {
        if(startNode.visited){
            return;
        }
        startNode.visited = true;
        System.out.println("Visited "+startNode.data);
        for(Node node: startNode.AdjacentNodes){
            if(!node.visited){
                visitUsingDFS(node);
            }
        }
    }
于 2014-11-09T04:17:06.917 回答