时间戳

首页 > 解决方案 > 如何使用 BFS 重建路径

c++ - 如何使用 BFS 重建路径

问题描述

我了解到广度优先搜索是一种可用于计算两个节点之间最短距离的算法。我在下面的代码中实现了 BFS 算法：

#define N 4 
#define M 4 

// QItem for current location and distance 
// from source location 
class QItem {
public:
    int row;
    int col;
    int dist;
    QItem(int x, int y, int w)
        : row(x), col(y), dist(w)
    {
    }
};


int minDistance(char grid[N][M])
{
    QItem source(0, 0, 0);

    // To keep track of visited QItems. Marking 
    // blocked cells as visited. 
    bool visited[N][M];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
        {
            if (grid[i][j] == '0')
                visited[i][j] = true;
            else
                visited[i][j] = false;

            // Finding source 
            if (grid[i][j] == 's')
            {
                source.row = i;
                source.col = j;
            }
        }
    }

    // applying BFS on matrix cells starting from source 
    queue<QItem> q;
    q.push(source);
    visited[source.row][source.col] = true;
    while (!q.empty()) {
        QItem p = q.front();
        q.pop();

        if (grid[p.row][p.col] == 'd')
            return p.dist;

        if (p.row - 1 >= 0 && visited[p.row - 1][p.col] == false) {
            q.push(QItem(p.row - 1, p.col, p.dist + 1));
            visited[p.row - 1][p.col] = true;
        }

        if (p.row + 1 < N && visited[p.row + 1][p.col] == false) {
            q.push(QItem(p.row + 1, p.col, p.dist + 1));
            visited[p.row + 1][p.col] = true;
        }

        if (p.col - 1 >= 0 && visited[p.row][p.col - 1] == false) {
            q.push(QItem(p.row, p.col - 1, p.dist + 1));
            visited[p.row][p.col - 1] = true;
        }

        if (p.col + 1 < M && visited[p.row][p.col + 1] == false) {
            q.push(QItem(p.row, p.col + 1, p.dist + 1));
            visited[p.row][p.col + 1] = true;
        }
    }
    return -1;
}

int main()
{
    char grid[N][M] = { { '0', '*', '0', 's' },
                        { '*', '0', '*', '*' },
                        { '0', '*', '*', '*' },
                        { 'd', '*', '*', '*' } };

    cout << minDistance(grid);
    return 0;
}

我的问题是，是否存在一种有效的方法来重建两个节点之间的路径而不运行另一种算法？如果没有，是否有另一种可以重建路径的最短路径算法？

标签： c++algorithmbreadth-first-search

解决方案

要使用 重建路径breadth-first search，您可以保留一个vector跟踪每个节点的父节点的父节点。BFS 完成运行后，您可以从末端节点向后追溯至起点以构建您的路径。

这是一些说明这一点的代码：

while(!Q.empty){
    int curr = Q.front();
    Q.pop();

    if(curr == destination){break;}

    for(int item : adj[curr]){ // for every element adjacent to curr
        if(!visited[item]){
            visited[item] = true;
            parent[item] = curr; // connects curr to item
            Q.push(item);
        }
    }
}

// trace from the destination back to the start
int tracer = destination;
vector <int> path = {tracer};

while(tracer != start){
    tracer = parent[tracer];
    path.push_back(tracer);
}

// note that this constructs path in reverse order (from end to start)

在您的情况下，parent应该是一个map <QItem, QItem>，跟踪每个QItem's父母。

推荐阅读