如何找到BFS找到的实际路径？

Question

15

我试图解决的问题涉及地铁系统的树形结构。

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

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

我可以编写代码保存BFS搜索所有点所需的所有信息，但我的主要关注点是，即使BFS正确找到该点，我如何知道它的路径？

BFS将搜索每个级别，当其中一个级别到达我的目标时，它将跳出运行循环，然后，我将获得一个访问队列和一个未访问队列，当访问队列填满BFS搜索的每个节点时，我应该如何告诉用户需要访问哪些站点？

- Shane Hsu

哪里是要忽略的中文单词？ - mahmood

@mahmood 在我发布的图片上。 - Shane Hsu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

为了实现这一点，您需要存储一个 map:V->V （从顶点到顶点），它将为每个节点 v 映射“发现”v的顶点 u。

在 BFS 的迭代过程中，您将填充此映射表。

稍后，您可以通过简单地从目标节点（在映射表中）开始向上移动，直到返回源节点来重构路径，那将是你的路径（当然要反转）。

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