使用BFS存储和打印最短路径

Question

我正在使用广度优先搜索(因此一个队列(从x1.x2.x3.x4.x4(例如0.0.0.0.3.0(的位置获得0.0.0.0.0。我能够实现目标。我只需要打印到它的最短路径。我认为跟踪指向父母的指针会起作用。但是，到目前为止，我每个代码都在更新上述指针时遇到了很多麻烦。

class Position {
private:
    static int move;        
    vector<int> pos;        
    Position* start;
    Position* next;
    static int ctorCounter;
    static int dtorCounter;
public:
    Position();
    Position(vector<int>);
    ~Position();
    void setNext(Position*);
    int getCounter();
    Position* afterMove(int);
    bool isDone();
    bool operator==(Position&);
    friend ostream& operator<<(ostream&, const Position&);
};
void Position::setNext(Position* P) {
    Position* cursor = start;   
    if(ctorCounter == 1) {
        start = P;
    }
    else {
        cursor->next = P;
        cursor = cursor->next;
    }
}
while(!posQueue.empty()) {
    Position* before = posQueue.front();
    //cout << *before << endl;
    if(before->isDone()) {
        break;
    }
    for(int k = 1; k <= 5; k++) {               
        Position* after = before->afterMove(k);
        if(after != nullptr) {
            P.setNext(after);
            posQueue.push(after);
        }       
    }   
    posQueue.pop();
}

Answer 1

bfs不会帮助您在从点到点找到最短的路径，如Kruskal的最小跨越树和Dijkstra的最短路径算法，以找到最短的路径。