In tất cả đường đi từ nguồn đến đích (DFS) trong C++

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

Ví dụ đồ thị:

Source = K, Destination = P

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

Giải pháp: DFS từ nguồn, đánh dấu visited, lưu đường đi. Khi đến đích, in đường đi. Backtrack bỏ đánh dấu.

Chương trình minh họa

#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 {
        for (int v : adj[u])
            if (!visited[v]) findNewPath(v, 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 << "Tất cả đường đi từ " << s << " đến " << d << ":\n";
    g.printPaths(s, d);
    return 0;
}

Kết quả

2 0 1 3
2 0 3
2 1 3