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

我要解决的问题与捷运系统树有关。

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

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

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

BFS将搜索每个级别，当其中一个级别到达我的目的地时，它将跳出运行循环，然后，我将获得一个访问队列和一个未访问队列，我该如何告诉用户他需要什么停止当BFS搜索过的每个节点都充满了访问队列时，该如何访问？

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

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

稍后-您可以通过简单地从目标节点（在地图中）向上直到返回源（这就是您的路径，当然是反向的）来重建路径。

请注意，如果您列举了顶点，则可以将该地图实现为数组。