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

ในปัญหานี้ เราจะได้รับ directed graph และต้องพิมพ์เส้นทางทั้งหมดจาก source ไป destination ของ graph

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

เพื่อแก้ปัญหานี้ เราจะท่อง graph โดยใช้เทคนิค depth-first search เริ่มจาก source เราจะท่องแต่ละ vertex เก็บใน path array และ mark ว่า visited (เพื่อไม่ให้เยี่ยมชม vertex เดียวกันซ้ำ) และพิมพ์ path นี้เมื่อถึง destination vertex

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

#include <iostream>
#include <list>
using namespace std;

class Graph {
    int V;
    list<int> *adj;
    void findNewPath(int, int, bool[], int[], int&);
public:
    Graph(int V);
    void addEdge(int u, int v);
    void printPaths(int s, int d);
};

Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int u, int v) {
    adj[u].push_back(v);
}

void Graph::printPaths(int s, int d) {
    bool *visited = new bool[V];
    int *path = new int[V];
    int path_index = 0;
    for (int i = 0; i < V; i++)
        visited[i] = false;
    findNewPath(s, d, visited, path, path_index);
}

void Graph::findNewPath(int u, int d, bool visited[], int path[], int &path_index) {
    visited[u] = true;
    path[path_index] = u;
    path_index++;
    if (u == d) {
        for (int i = 0; i < path_index; i++)
            cout << path[i] << " ";
        cout << endl;
    }
    else {
        list<int>::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
            if (!visited[*i])
                findNewPath(*i, d, visited, path, path_index);
    }
    path_index--;
    visited[u] = false;
}

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(2, 0);
    g.addEdge(2, 1);
    g.addEdge(1, 3);
    int s = 2, d = 3;
    cout << "Following are all different paths from source to destination : \n";
    g.printPaths(s, d);
    return 0;
}

ผลลัพธ์

Following are all different paths from source to destination :
2 0 1 3
2 0 3
2 1 3