นับเส้นทางทั้งหมดจากต้นทางถึงปลายทางที่มีขอบ K ขอบใน C++

ในบทช่วยสอนนี้ เราจะอภิบายโปรแกรมเพื่อหาจำนวนเส้นทางจากต้นทางถึงปลายทางที่มีขอบทั้งหมด K ขอบ

สำหรับเรื่องนี้ เราจะได้รับกราฟและค่าของต้นทางและปลายทาง งานของเราคือหาเส้นทางทั้งหมดที่เป็นไปได้เริ่มจากต้นทางถึงปลายทางที่มีขอบทั้งหมด K ขอบ

ตัวอย่าง

#include <iostream>
using namespace std;
#define V 4

// counting walks using recursion
int countwalks(int graph[][V], int u, int v, int k) {
    if (k == 0 && u == v)
        return 1;
    if (k == 1 && graph[u][v])
        return 1;
    if (k <= 0)
        return 0;
    int count = 0;
    // moving to the adjacent nodes
    for (int i = 0; i < V; i++)
        if (graph[u][i] == 1)
            count += countwalks(graph, i, v, k - 1);
    return count;
}

int main() {
    int graph[V][V] = {
        {0, 1, 1, 1},
        {0, 0, 0, 1},
        {0, 0, 0, 1},
        {0, 0, 0, 0}
    };
    int u = 0, v = 3, k = 2;
    cout << countwalks(graph, u, v, k);
    return 0;
}

เอาต์พุต

2