In tất cả đường đi từ nguồn đến đích bằng BFS trong C++

Cho đồ thị có hướng, in tất cả đường đi từ nguồn đến đích bằng BFS.

Ví dụ đồ thị:

Source = K, Destination = P

K -> T -> Y -> A -> P
K -> T -> Y -> P
K -> A -> P

Giải pháp: Dùng queue lưu đường đi (vector). BFS: lấy đường đi từ queue, nếu đỉnh cuối = đích thì in. Ngược lại, mở rộng các đỉnh kề chưa thăm trong đường đi hiện tại.

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;
void printPath(vector<char>& path){
    for (char c : path) cout << c << " ";
    cout << endl;
}
int isVertexVisited(char x, vector<char>& path){
    for (char c : path) if (c == x) return 1;
    return 0;
}
void pathSourceToDestination(vector<vector<char> >& g, char src, char dst, int v){
    queue<vector<char> > q;
    vector<char> path = {src};
    q.push(path);
    while (!q.empty()){
        path = q.front(); q.pop();
        char last = path.back();
        if (last == dst) printPath(path);
        for (char next : g[last]){
            if (!isVertexVisited(next, path)){
                vector<char> newpath = path;
                newpath.push_back(next);
                q.push(newpath);
            }
        }
    }
}
int main(){
    vector<vector<char> > g(256);
    g['X'].push_back('S'); g['X'].push_back('A'); g['X'].push_back('N');
    g['A'].push_back('S'); g['N'].push_back('X'); g['N'].push_back('A');
    char src = 'N', dst = 'S';
    cout << "Đường đi từ " << src << " đến " << dst << ":\n";
    pathSourceToDestination(g, src, dst, 4);
    return 0;
}

Kết quả

N X S
N A S
N X A S