พิมพ์เส้นทางทั้งหมดจาก Source ไป Destination ด้วย BFS ใน C++

ในปัญหานี้ เราจะได้รับ directed graph และต้องพิมพ์เส้นทางทั้งหมดจาก source ไป destination ของ graph โดยใช้ Breadth First Search (BFS)

Directed graph คือ graph ที่ edges มีทิศทางจาก vertex a ไป b

ตัวอย่างเพื่อความเข้าใจ

Source = K destination = P

Output

K → T → Y → A → P
K → T → Y → P
K → A → P

ที่นี่ เราพบ paths จาก K ไป P เราได้ท่อง paths และพิมพ์ paths ทั้งหมดจาก K ที่นำไปสู่ P

เพื่อพิมพ์เส้นทางทั้งหมดจาก source ไป destination เราจะต้องท่อง graph และเก็บ paths แล้วพิมพ์ valid paths

ในกรณีของ DFS กระบวนการง่าย แต่ในกรณี BFS จะซับซ้อนกว่านิดหน่อย

เพื่อแก้ปัญหานี้ เราจะต้องใช้ queue ที่จะเก็บ paths เริ่มจาก source node เราจะเริ่มท่อง array โดยใช้ BFS ท่อง tree และตรวจสอบใน queue ถ้าเจอ destination vertex ให้พิมพ์ queue elements มิฉะนั้นข้ามไป

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

void printPath(vector<char> &path) {
    int size = path.size();
    for (int i = 0; i < size; i++)
        cout << path[i] << " ";
    cout << endl;
}

int isVertexVisited(char x, vector<char> &path) {
    int size = path.size();
    for (int i = 0; i < size; i++)
        if (path[i] == x)
            return 1;
    return 0;
}

void pathSourceToDestination(vector<vector<char> > &g, char src, char dst, int v) {
    queue<vector<char> > q;
    vector<char> path;
    path.push_back(src);
    q.push(path);
    while (!q.empty()) {
        path = q.front();
        q.pop();
        char last = path[path.size() - 1];
        if (last == dst)
            printPath(path);
        for (int i = 0; i < g[last].size(); i++) {
            if (!isVertexVisited(g[last][i], path)) {
                vector<char> newpath(path);
                newpath.push_back(g[last][i]);
                q.push(newpath);
            }
        }
    }
}

int main() {
    vector<vector<char> > g;
    int v = 4;
    g.resize(4);
    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 << "path from src " << src << " to dst " << dst << " are \n";
    pathSourceToDestination(g, src, dst, v);
    return 0;
}

ผลลัพธ์

path from src N to dst S are
N X S
N A S
N X A S