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 | times | E |,因为我们没有迭代图中每个顶点的所有边.

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

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

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

引自Cormen,

"排队和出队的操作花费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(()in((adj)中的一些O(1)指令{有些O(1)指令}

问题是这里执行了多少指令？这将是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 和每个顶点/节点的相邻顶点作为这些顶点的列表。在循环图的情况下，您必须“查看”所有框以检查它是否已被“访问”，或者如果它是树状图，则您只需遍历所有子项