寻找一种很好的方法来跟踪两个节点之间的广度优先遍历,而又不了解任何图形.相对于“深度优先”(如果没有平移,您可以丢弃路径)在遍历期间可能有很多“开放”的可能性.

解决方法:

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