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

Question

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

看起来像这样：

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

在第一种情况下，我使用 BFS、DFS、Dijkstra 的算法来找到从节点 0 到所有其他节点的最短路径，在第二种情况下我对节点 55（起始节点）做同样的事情，在第三种情况下我对节点 99 做同样的事情。

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

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

顺便说一下，它是用 C++ 实现的，向量的向量用于存储图形。

非常感谢您提前。

Answer 1

首先：您是否多次运行它？结果可能会有很大差异。

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

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