7.10. 广度优先搜索分析¶
7.10. Breadth-First Search Analysis
在继续其他图算法之前，让我们分析广度优先搜索算法的运行时间性能。首先需要观察的是，while 循环至多执行一次每个图中的顶点（最多 \(|V|\) 次迭代）。这点是正确的，因为一个顶点必须是白色的，才能被检查并加入队列。这使得 while 循环的时间复杂度为 \(O(|V|)\)。for 循环嵌套在 while 循环中，它的执行次数至多为每条边一次（最多 \(|E|\) 次迭代）。原因是每个顶点至多被出队一次，并且我们仅在顶点 \(u\) 被出队时检查从节点 \(u\) 到节点 \(v\) 的边。这使得 for 循环的时间复杂度为 \(O(|E|)\)。将这两个循环结合起来，我们得到的时间复杂度是 \(O(|V| + |E|)\)。
当然，进行广度优先搜索只是任务的一部分。另一部分任务是从起始节点到目标节点的路径追踪。最坏的情况是图是一个单一的长链。在这种情况下，遍历所有顶点的时间复杂度是 \(O(|V|)\)。正常情况下，时间复杂度将是 \(|V|\) 的某个分数，但我们仍会写作 \(O(|V|)\)。
最后，至少对于这个问题，还需要时间来构建初始图。我们将 build_graph 函数的分析留给你作为练习。
Before we continue with other graph algorithms, let’s analyze the run time performance of the breadth-first search algorithm. The first thing to observe is that the while loop is executed, at most, one time for each vertex in the graph (up to \(|V|\) iterations). You can see that this is true because a vertex must be white before it can be examined and added to the queue. This gives us \(O(|V|)\) for the while loop. The for loop, which is nested inside the while, is executed at most once for each edge in the graph (up to \(|E|\) iterations). The reason is that every vertex is dequeued at most once and we examine an edge from node \(u\) to node \(v\) only when node \(u\) is dequeued. This gives us \(O(|E|)\) for the for loop. Combining the two loops gives us \(O(|V| + |E|)\).
Of course doing the breadth-first search is only part of the task. Following the links from the starting node to the goal node is the other part of the task. The worst case for this would be if the graph was a single long chain. In this case traversing through all of the vertices would be \(O(|V|)\). The normal case is going to be some fraction of \(|V|\) but we would still write \(O(|V|)\).
Finally, at least for this problem, there is the time required to build the initial graph. We leave the analysis of the build_graph function as an exercise for you.
创建日期: 2024年9月9日