BFS和DFS运行时的说明 [英] Explanation of runtimes of BFS and DFS

问题描述

为什么BFS和DFS O（V + E）的运行时间，特别是当有一个节点具有可从顶点到达的节点的有向边，就像在下面的站点

Why are the running times of BFS and DFS O(V+E), especially when there is a node that has a directed edge to a node that can be reached from the vertex, like in this example in the following site

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

推荐答案

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

E is the set of all edges in the graph, as G={V,E}. So, |E| is count of all edges in the graph.

这本身应该足以说服你，整体的复杂性不能是| V | times | E |，因为我们不会遍历每个顶点的图形中的所有边。

This alone should be enough to convince you that the overall complexity can't be |V| times |E|, since we are not iterating over all the edges in the graph for each vertex.

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

In the adjacency list representation, for each vertex v, we only traverse those nodes which are adjacent to it.

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

The |V| factor of the |V|+|E| seems to come from the number of queue operations done.

请注意，算法的复杂性取决于所使用的数据结构。
有效地访问了图形表示中存在的每条信息，这就是为什么图形的矩阵表示，复杂度变成V平方。

Note that the complexity of the algorithm depends on the data structure used. effectively we are visiting each piece of information present in the representation of the graph, which is why for matrix representation of the graph, complexity becomes V squared.

从Cormen引用

入队和出队的操作取O（1）时间，所以用于队列操作的总时间为O（V），因为邻接每个顶点的列表仅在顶点出现时被扫描，每个邻接列表最多被扫描一次，由于所有邻接列表的长度之和为Θ（E），所以在扫描邻接列表中花费的总时间为O（ E）初始化的开销是O（V），因此BFS的总运行时间为O（V + E）。

"The operations of enqueuing and dequeuing take O(1) time, so the total time devoted to queue operations is O( V). Because the adjacency list of each vertex is scanned only when the vertex is dequeued, each adjacency list is scanned at most once. Since the sum of the lengths of all the adjacency lists is Θ(E), the total time spent in scanning adjacency lists is O( E). The overhead for initialization is O( V), and thus the total running time of BFS is O( V + E)."

这篇关于BFS和DFS运行时的说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！