c++ - 在图上实现 BFS

Question

我在图中有代表城镇的顶点。我试图找到从 A 点到 B 点的最短路径。

我创建了一个图形类。

struct Edge{
    string name;
    vector< Edge *> v;
    Edge( string n ){
        name = n;
    }
};

class Graph{
public:
        Graph(){};
        void addEdge( string start_point , string end_point){
            graph[ start_point ] -> v.push_back( graph[ end_point ]);
        }
        void addPeak( string name ){
            graph[name] = new Edge(name);
            size++;
        }
        void printPeaks(){
            for( auto &a : graph){
                cout << a . first << endl;
            }
        }
    void getRoad( string starting , string ending ){
        map< string , bool > visited;
        queue< Edge * > q;

        for( auto &a : graph ){
            visited[ a.first ] = false;
        }

        q.push( graph[starting] );
        while( ! q.empty( )){
                Edge *tmp = q.front();
                q.pop();
                cout << tmp -> name << endl;
                if( tmp -> name  == ending ){
                        cout << "found " << endl;
                        break;
                }
                for( unsigned int i = 0; i < tmp -> v.size() ; i++){
                    q.push( tmp -> v [i]);
                }

        }
    }
private:
    map< string , Edge *> graph;
    int size = 0;
};

我按如下方式添加顶点和边。

Graph g;
    g.addPeak("Prague");
    g.addPeak("Bratislava");
    g.addPeak("Budapest");
    g.addPeak("Berlin");
    g.addPeak("Moscow");
    g.addPeak("London");
    g.addEdge("Bratislava", "Berlin");
    g.addEdge("Bratislava" , "Budapest");
    g.addEdge("Bratislava" , "London");
    g.addEdge("Berlin" , "Moscow");
    g.addEdge("Budapest" , "Berlin");
    g.getRoad("Bratislava", "Moscow");

在最后一行，我想找到从布拉迪斯拉发到莫斯科的最短路径。正如我在代码中演示的那样，我可以找到路径，但与此同时，所有其他与布拉迪斯拉发有优势的城镇也会被打印出来。而不是想要的输出

Bratislava 
Berlin
Moscow

它打印以下列表。

Bratislava
Berlin
Budapest
London
Moscow

如何存储和打印我想要的路径？

Answer 1

无需给出明确的实现细节，这可以按如下方式完成。

1. 您可以使用用户定义的堆栈来显式存储当前访问过的城市。当到达目标城市时，堆栈包含到城市的路径。

2. 您的实现没有使用单独的类型来表示节点。没有什么不妥。但是，如果它将使用单独的类型，则可以为该类型赋予对另一个节点的父引用。如果算法遵循边，则访问节点的父引用将设置为发起访问的节点。这样，在到达目标节点时，可以按照这些引用生成所需的路径。

3. 由于实现缺少节点的单独类型，辅助字典(使用城市名称作为键和值，其中值是父城市)。在到达目标节点时，可以通过迭代地跟随字典中的父节点来生成所需的路径。这种方法将使用与第 2 点中相同的想法，而无需为节点引入新类型。