BFS路径回溯中指针指向局部变量失效问题求助

问题背景 #

我正在实现可回溯路径的BFS（广度优先搜索）算法，希望通过指针建立步骤间的关联。其中sx、sy为起点坐标，tx、ty为终点坐标，act[][]是用于避免重复访问的布尔表。

核心代码实现如下：

struct trip
{
    int first;
    int second;
    trip* last;
};

void write(trip a)
{
    cout<<"\n";
    cout<< "x" << " " << a.first << "\n";
    cout<< "y" << " " << a.second << "\n";
    cout<< "x lasta" << " " << a.last->first << "\n";
    cout<< "y lasta" << " " << a.last->second << "\n";
}

queue<trip> Q;
trip P; P.first = sx; P.second = sy; P.last = nullptr; Q.push(P);
while(!Q.empty())
{
    trip temp = Q.front(); Q.pop();
    if(temp.last != nullptr)
        write(temp);

    int corx = temp.first;  int cory = temp.second;

    if(corx == tx && cory == ty)
    {
        // 找到终点
    }

    if(act[corx][cory] == false)
    {
        act[corx][cory] = true;

        // 上
        if(cory - 1 >= 0)
        {
            trip TEMPUUS; TEMPUUS.first = corx - 1; TEMPUUS.second = cory; TEMPUUS.last = &temp; Q.push(TEMPUUS);
            cout << corx - 1 << " " << TEMPUUS.last -> first;
        }

        // 下
        if(cory + 1 <= 2000)
        {
            trip TEMPUUS; TEMPUUS.first = corx + 1; TEMPUUS.second = cory; TEMPUUS.last = &temp; Q.push(TEMPUUS);
        }

        // 左
        if(corx - 1 >= 0)
        {
            trip TEMPUUS; TEMPUUS.first = corx; TEMPUUS.second = cory - 1; TEMPUUS.last = &temp; Q.push(TEMPUUS);
        }

        // 右
        if(corx + 1 <= 2000)
        {
            trip TEMPUUS; TEMPUUS.first = corx; TEMPUUS.second = cory + 1; TEMPUUS.last = &temp; Q.push(TEMPUUS);
        }
    }
}

问题现象 #

将trip变量入队时，其坐标与前驱节点不同，但进入队列的下一轮迭代后，局部变量temp超出作用域被销毁，导致新节点的last指针指向非法内存，出现指针失效、访问非法内存的问题。

完整代码示例：

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

struct trip
{
    int first;
    int second;
    trip* last;
};

void write(trip a)
{
    cout << "\n";
    cout <<  "x" << " " << a.first << "\n";
    cout <<  "y" << " " << a.second << "\n";
    cout <<  "x lasta" << " " << a.last->first << "\n";
    cout <<  "y lasta" << " " << a.last->second << "\n";
}

void bfs(int sx, int sy, int tx, int ty)
{
    queue<trip> Q;
    trip P; P.first = sx; P.second = sy; P.last = nullptr; Q.push(P);
    int test = 0;
    while(!Q.empty())
    {
        trip temp = Q.front(); Q.pop();
        if(temp.last != nullptr)
            write(temp);
        int corx = temp.first;
        int cory = temp.second;

        if(act[corx][cory] == false)
        {
            act[corx][cory] = true;

            // 上
            if(cory - 1 >= 0)
            {
                trip TEMPUUS; TEMPUUS.first = corx - 1; TEMPUUS.second = cory; TEMPUUS.last = &temp; Q.push(TEMPUUS);
                cout << corx - 1 << " " << TEMPUUS.last -> first;
            }
        }
        test++;
        if(test > 5)
            return;
    }
}

int main()
{
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    sx += 1000; sy += 1000; tx += 1000; ty += 1000;
    bfs(sx, sy, tx, ty);
    return 0;
}

问题根源 #

代码中temp是栈上的局部变量，当当前循环迭代结束后，temp会被销毁，内存被释放。而新创建的TEMPUUS节点的last指针指向的是&temp，也就是这个即将被销毁的局部变量的地址。后续访问这个指针时，内存已经不属于原来的temp，属于非法访问，导致未定义行为。

解决方案 #

方案1：使用动态分配内存（new） #

将trip对象分配在堆上，这样即使局部变量生命周期结束，堆内存也不会被自动释放，指针仍然有效。注意最后要手动释放内存避免内存泄漏。

修改后的核心代码：

queue<trip*> Q; // 队列存储指针
trip* P = new trip; 
P->first = sx; 
P->second = sy; 
P->last = nullptr; 
Q.push(P);

while(!Q.empty())
{
    trip* temp = Q.front(); Q.pop();
    if(temp->last != nullptr)
        write(*temp); // 解引用传值

    int corx = temp->first;  
    int cory = temp->second;

    if(corx == tx && cory == ty)
    {
        // 回溯路径并释放内存
        trip* curr = temp;
        while(curr != nullptr)
        {
            cout << "(" << curr->first << "," << curr->second << ")\n";
            trip* next = curr->last;
            delete curr;
            curr = next;
        }
        break;
    }

    if(act[corx][cory] == false)
    {
        act[corx][cory] = true;

        // 上
        if(cory - 1 >= 0)
        {
            trip* TEMPUUS = new trip; 
            TEMPUUS->first = corx - 1; 
            TEMPUUS->second = cory; 
            TEMPUUS->last = temp; 
            Q.push(TEMPUUS);
        }

        // 其他方向同理修改...
    }
}

方案2：记录前驱坐标而非指针 #

不需要使用指针，而是维护一个二维数组prev[][]，每个位置存储到达该点的前驱坐标（比如用pair或者自定义结构体）。这种方式更安全，避免指针问题，也是BFS路径回溯的常用方法。

示例实现：

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

// 定义坐标类型
using Point = pair<int, int>;

void bfs(int sx, int sy, int tx, int ty)
{
    queue<Point> Q;
    vector<vector<bool>> act(2001, vector<bool>(2001, false));
    vector<vector<Point>> prev(2001, vector<Point>(2001, {-1, -1})); // 存储前驱坐标

    Q.push({sx, sy});
    act[sx][sy] = true;

    bool found = false;
    // 方向数组：上、下、左、右
    vector<Point> dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};

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

        int x = curr.first;
        int y = curr.second;

        if(x == tx && y == ty)
        {
            found = true;
            break;
        }

        for(auto& dir : dirs)
        {
            int nx = x + dir.first;
            int ny = y + dir.second;
            if(nx >=0 && nx <=2000 && ny >=0 && ny <=2000 && !act[nx][ny])
            {
                act[nx][ny] = true;
                prev[nx][ny] = curr;
                Q.push({nx, ny});
            }
        }
    }

    // 回溯路径
    if(found)
    {
        vector<Point> path;
        Point curr = {tx, ty};
        while(curr.first != -1 && curr.second != -1)
        {
            path.push_back(curr);
            curr = prev[curr.first][curr.second];
        }
        // 反转路径得到从起点到终点的顺序
        reverse(path.begin(), path.end());
        cout << "路径：\n";
        for(auto& p : path)
        {
            cout << "(" << p.first -1000 << "," << p.second -1000 << ")\n"; // 还原原始坐标
        }
    }
    else
    {
        cout << "无路径可达\n";
    }
}

int main()
{
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    sx += 1000; sy += 1000; tx += 1000; ty += 1000;
    bfs(sx, sy, tx, ty);
    return 0;
}

方案3：使用智能指针（C++11及以上） #

用std::shared_ptr管理trip对象的生命周期，自动释放内存，避免手动管理的麻烦：

#include <memory>

// ...

queue<shared_ptr<trip>> Q;
auto P = make_shared<trip>();
P->first = sx;
P->second = sy;
P->last = nullptr;
Q.push(P);

while(!Q.empty())
{
    auto temp = Q.front();
    Q.pop();

    // ... 后续逻辑类似方案1，只是使用shared_ptr，无需手动delete
}

总结 #

方案2（记录前驱坐标）是最推荐的BFS路径回溯实现方式，无需处理指针的生命周期问题，代码更简洁安全。如果一定要使用指针关联节点，优先选择智能指针或手动管理堆内存，但要注意内存泄漏问题。

内容的提问来源于stack exchange，提问作者Milosz