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

发布时间：2020-12-16 05:47:44 所属栏目：百科来源：网络整理

导读：我试图解决的问题涉及一个MRT系统的树. 每个节点最多可以连接到4个点,这很简单.这是我的想法 struct stop { int path,id; stop* a; stop* b; stop* c; stop* d;}; 我可以编写代码来保存BFS所需的所有信息,以搜索所有要点,但我的主要关注点是,即使BFS找到正确

我试图解决的问题涉及一个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路径[当然…相反]

注意,如果枚举顶点,则可以将该映射实现为数组.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!