algorithm - 什么是指针追踪以及它与 BFS 的关系

Question

在阅读关于 BFS（广度优先搜索）的 PPT 时，我发现 BFS 可以用于我们有“指针追逐”的地方。指针追逐究竟是什么，它与 BFS 有什么关系？

Answer 1

指针意味着您的数据上的图表。BFS（广度优先搜索）是一种在该图中搜索的算法。

指针追逐只是跟随大量指针的另一个词。

Answer 2

从硬件角度（CPU）来看，指针追踪对性能不利，因为内存读取实际上是在 CPU 中序列化的（即没有 ILP）。在前一个完成之前，您不能开始读取（即加载指令）（因为之前的加载为我们提供了下一次加载的地址，依此类推......）。

Answer 3

我发现最容易想到一个Linked List例子。

假设我们有Linked List5 个元素。要到达第三个元素，您必须使用Pointer-chasing遍历元素。