問題描述

我試圖解決的問題與 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 找到的實際路徑?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！