BFS和DFS的运行时间解释

Question

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

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

Answer 1

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

Answer 2

这个问题花了我大约 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|。

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

Answer 3

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

Answer 4

当您将图形视为表示为相邻列表的数据结构时，它就会变得清晰

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

Answer 5

您迭代 |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);
            }
        }
    }