นับเส้นทางทั้งหมดระหว่างสองจุดยอดใน C++

ในบทช่วยสอนนี้ เราจะอภิบายโปรแกรมเพื่อหาจำนวนเส้นทางระหว่างสองจุดยอด

สำหรับเรื่องนี้ เราจะได้รับกราฟมีทิศทาง งานของเราคือหาจำนวนเส้นทางที่เป็นไปได้ระหว่างสองจุดยอดที่กำหนด

ตัวอย่าง

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

// constructing a directed graph
class Graph {
    int V;
    list<int> *adj;
    void countPathsUtil(int, int, bool[], int&);
public:
    // constructor
    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) {
    // marking all the vertices as not visited
    bool *visited = new bool[V];
    memset(visited, false, sizeof(visited));
    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 current vertex is same as destination, then increment count
    if (u == d)
        pathCount++;
    // if current vertex is not destination
    else {
        list<int>::iterator i;
        for (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;
}

เอาต์พุต

3