c++ - 在 C++ 中使用 BFS 的最短路径

Question

我必须编写一个算法来找到未加权图中的最短路径。我发现在未加权图中找到最短路径的最佳方法是简单地执行 BFS 并在到达目的地后停止。问题是我不知道如何跟踪通往该目的地的路径。

到目前为止，我考虑过为每个发现的新节点创建一个新的路径列表，但我不知道如何实现它。

就访问每个节点而言，这段代码似乎是有效的(有点乱，抱歉):

void shortestPath(string start, string finish, list< list<string> > adjList){

    queue< list< list<vertex*> >::iterator >    myQueue;
    list< list<vertex*> > listVertices = initializeVertices(start, adjList);
    list< list<vertex*> >::iterator aux = extractList(start, listVertices);

    myQueue.push(aux);

    while(myQueue.size() > 0){

        list< list<vertex*> >::iterator vert = myQueue.front();

        for(list<vertex*>::iterator it = vert->begin(); it != vert->end(); it++){
            if((*it)->color == "white"){
                (*it)->color = "gray";
                myQueue.push(extractList((*it)->name, listVertices));
            }

        }

        list<vertex*>::iterator vertAux = vert->begin();
        (*vertAux)->color = "black";
        myQueue.pop();
    }
}

有什么想法吗？

Answer 1

您可以通过为每个顶点 v 保存最短路径树中 v 的父节点的名称来存储最短路径树。然后，您可以按照这些父指针重建所需的最短路径，直到到达源顶点。