如何找到 BFS 找到的实际路径? [英] How can I find the actual path found by BFS?

问题描述

我试图解决的问题与 MRT 系统树有关.

The problem I'm trying to solve concerns a tree of MRT system.

每个节点最多可以连接4个点，这大大简化了事情.这是我的想法.

Each node can be connected to 4 points at most, which simplify thing by a lot. Here's my thought.

struct stop {
    int path, id;
    stop* a;
    stop* b;
    stop* c;
    stop* d;
};

我可以编写代码来保存 BFS 搜索所有点所需的所有信息，但我主要担心的是，即使 BFS 正确找到了该点，我怎么知道它的路径?

I can write code to save all the information I need for BFS to search for all the points, but my main concern is that, even though BFS finds the point properly, how can I know its path?

BFS会搜索每一层，当其中一个到达我的目的地时，它会跳出run loop，然后，我会得到一个已访问队列和一个未访问队列，我该怎么告诉用户什么当访问的队列被 BFS 搜索到的每个节点都填满时，他需要访问的站点?

BFS will search each level, and when one of it reaches my destination, it will jump out of the run loop, and then, I will get a visited queue and an unvisited queue, how am i supposed to tell the user what stops he needs to visit when the visited queue is filled with every nodes BFS has searched?

推荐答案

为此，您需要存储一个 map:V->V(从顶点到顶点)，它将映射从每个节点v，发现"v的顶点u.

To do so, you need to store a map:V->V (from vertices to vertices), which will map from each node v, the vertex u that "discovered" v.

您将在 BFS 迭代期间填充此地图.

You will populate this map during the iterations of BFS.

稍后 - 您可以通过简单地从目标节点(在地图中)直到返回源节点来重建路径，这将是您的路径(当然是相反的).

Later - you can reconstruct the path by simply going from the target node (in the map) up until you get back to the source, which will be your path (reversed, of course).

请注意，如果枚举顶点，则此映射可以实现为数组.

Note that this map can be implemented as an array if you enumerate the vertices.

这篇关于如何找到 BFS 找到的实际路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！