search - 如何使用广度优先搜索获取 2 个节点之间的路径？

Question

我试图在图中的两个节点之间找到一条路径，其中边未加权。

我正在使用广度优先搜索，它在找到目标时停止，以查找路径的存在，但我不确定如何获取路径本身。

我尝试查看已访问节点的列表，但这似乎没有帮助。我看到有人使用 prolog 回答了这个问题，但我是一名 C++ 程序员。

我也看过Dijkstras algorithm，但这似乎有点过头了，因为一个简单的广度优先搜索几乎让我一路走来。

如何使用广度优先搜索获取 2 个节点之间的路径？

Answer 1

在您的节点结构中，您添加一个名为的变量parentNode，它是路径中该节点的父节点。最后，您可以通过从目标节点向后遍历来检索路径。

Answer 2

我发现这个简单的算法将节点的路径与队列中的节点一起存储在这里：https ://stackoverflow.com/a/50575971/5883177 所以当我们从队列中弹出一个节点时，我们也得到了路径那个节点很容易。

链接中的代码在 python 中，它使用元组来存储对。这是使用 std::pair 的 C++ 实现。

bool findPath(Node *n1, Node *n2, vector<Node*> &path)
{
    // We use queue to perform a BFS traversal and in addition to storing the
    // node we'll also store the path so far to the node.
    queue<pair<Node*,vector<Node*>>> q;
    
    // Visit the first node and add it to the queue.
    n1->visited=1;
    // Form the path, create a pair and add it the queue.
    vector<Node*> p;
    p.push_back(n1);
    q.push(make_pair(n1,p));
    
    while(!q.empty())
    {
        pair<Node*,vector<Node*>> curPair = q.front();
        q.pop();
        
        // visit all the unvisited nodes and check if there is n2 in it.
        for(Node *u : curPair.first->adjNodes ){
            if(u->visited == 0){
                
                if(u->value == n2->value){
                    // found our destination. Return true
                    // form the path by appending this node to the path till now
                    curPair.second.push_back(u);
                    // update the passed 'path' vector with the path so far.
                    path = curPair.second; // all nodes will be copied into path
                    return true;
                }
                
                // Not our node, visit the node if unvisited
                if(u->visited == 0){
                    u->visited = 1;
                    // Create a new path with this node added.
                    // Path so far can be obtained from the pair in queue
                    vector<Node*> newPath(curPair.second);
                    newPath.push_back(u);
                    // Add the node and the path to it into the queue.
                    q.push(make_pair(u, newPath));
                }
            }
        }
    }
    
    return false;
}


class Node{
    public:
    Node(int val) 
    { 
        value = val; 
        visited=0; 
    }
        
    int value;
    vector<Node*> adjNodes;
    int visited;
};