我试图解决的问题涉及一个MRT系统的树.
每个节点最多可以连接到4个点,这很简单.这是我的想法
struct stop {
int path,id;
stop* a;
stop* b;
stop* c;
stop* d;
};
我可以编写代码来保存BFS所需的所有信息,以搜索所有要点,但我的主要关注点是,即使BFS找到正确的点,我如何知道它的路径？
BFS将搜索每个级别,当其中一个到达目的地时,它将跳出运行循环,然后我将获得一个访问队列和一个未访问的队列,我应该如何告诉用户他需要什么停止访问队列是否填满BFS搜索的每个节点时访问？
解决方法
要这样做,您需要存储一个地图：V-> V [从顶点到顶点],其将从每个节点映射v,“发现”v的顶点u.
您将在BFS的迭代期间填充此地图.
稍后 – 您可以通过简单地从目标节点[在地图中]重建路径,直到您回到源头,并且它是yor路径[当然…相反]
注意,如果枚举顶点,则可以将该映射实现为数组.
