Đếm tất cả đường đi giữa hai đỉnh trong C++

Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng đường đi giữa hai đỉnh.

Cho một đồ thị có hướng. Nhiệm vụ là tìm số đường đi giữa hai đỉnh cho trước.

Ví dụ

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

class Graph {
    int V;
    list<int> *adj;
    void countPathsUtil(int, int, bool[], int&);
public:
    Graph(int V);
    void addEdge(int u, int v);
    int countPaths(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);
}

int Graph::countPaths(int s, int d) {
    bool *visited = new bool[V];
    memset(visited, false, V * sizeof(bool));
    int pathCount = 0;
    countPathsUtil(s, d, visited, pathCount);
    return pathCount;
}

void Graph::countPathsUtil(int u, int d, bool visited[], int &pathCount) {
    visited[u] = true;
    if(u == d) pathCount++;
    else {
        for(auto i = adj[u].begin(); i != adj[u].end(); ++i)
            if(!visited[*i])
                countPathsUtil(*i, d, visited, pathCount);
    }
    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 << g.countPaths(s, d);
    return 0;
}

Kết quả

3