c++ - 为什么 BFS 对同一张图中的不同节点位置给出不同的运行时间？

Question

我有一个折线图，它由 100 个节点组成，标记为 0 到 99。

看起来像这样:

0--1--2--3....98--99

我使用 BFS、DFS、Dijkstra 算法在第一种情况下找到从节点 0 到所有其他节点的最短路径，我对第二种情况下的节点 55(起始节点)和第三种情况下的节点 99 执行相同的操作.

但是在 BFS 中，最后一种情况所用的时间是第一种所用时间的两倍，但在这两种情况下节点位置在图形上是相同的。我在 中附上了运行时间.

BFS中的for和while循环访问次数相同，我想知道，为什么三种情况下访问时间不同？？

顺便说一句，它是用C++实现的，使用 vector 的 vector 来存储图形。

非常感谢您。

Answer 1

首先:您是否多次运行它？结果可能相差很大。

无论如何，很有可能是因为缓存问题。当您从 0 访问数组时，计算机通常工作得很好，因为它们会立即从您正在访问的索引中缓存(部分)数组。但是如果你从数组的末尾开始，它不会将整个数组放在快速缓存中。 (这对于 vector 没有什么不同，因为 vector 只是一个动态大小的数组)

另外，你不应该这样测试算法速度，你不能这样比较它们。因为如果你第一次运行 BFS，它还没有缓存整个数组。但是当您运行 DFS 时，整个阵列可能位于处理器的快速缓存中。我建议使用更大的图并检查稀疏图和密集图。此外，我会确保为每个算法编写单独的程序，以使用 time 等实用程序进行检查。