我有一个折线图，由 100 个节点组成，标记为从 0 到 99。
看起来像这样:
0--1--2--3....98--99
在第一种情况下，我使用 BFS、DFS、Dijkstra 算法找到从节点 0 到所有其他节点的最短路径，在第二种情况下，我对节点 55(起始节点)和第三种情况下的节点 99 执行相同的操作.
但是在 BFS 中，最后一种情况所花费的时间是第一种情况所花费时间的两倍，但是两种情况下节点位置在图形上是相同的。我已将运行时间附在
中.
BFS中的for和while循环被访问的次数相同，我想知道，为什么这三种情况花费的时间不同？
顺便说一下，它是用C++实现的，并且使用 vector 的 vector 来存储图。
提前非常感谢您。
最佳答案
首先:您是否运行过多次？结果可能会有很大差异。
无论如何，这很可能是由于缓存问题造成的。当您从 0 开始访问数组时，计算机通常工作得很好，因为它们会立即缓存您正在访问的索引中的数组(一部分)。但如果从数组末尾开始，则不会将整个数组放入快速缓存中。 (这对于 vector 来说没有什么不同，因为 vector 只是一个动态调整大小的数组)
此外，你不应该以这种方式测试算法速度，你不能像这样真正比较它们。因为如果您第一次运行 BFS，它根本还没有缓存整个数组。但是当您运行 DFS 时，整个阵列可能位于处理器的快速缓存中。我建议采用更大的图表并检查稀疏图和密集图。另外，我会确保为每个算法编写单独的程序，以使用诸如 time 之类的实用程序进行检查。
关于c++ - 为什么BFS对于同一个图中不同的节点位置给出不同的运行时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16968231/