C#图遍历——任意两个节点之间的跟踪路径

Question

寻找一种好的方法来跟踪两个节点之间的广度优先遍历，而无需对图一无所知。与深度优先(如果没有成功，您可以丢弃路径)相比，您在遍历过程中可能有很多“开放”的可能性。

Answer 1

天真的方法是构建一棵树，其中源节点作为根节点，其所有连接作为其子节点。根据您拥有的空间量，您可能需要随时消除循环。您可以使用位图来做到这一点，其中每个位对应于图中的一个不同节点。当您到达目标节点时，您可以沿着父链接返回到根节点，这就是您的路径。由于您采用的是广度优先，因此即使您不消除环路，也可以确信这是一条最短路径。