Đếm tất cả các bước đi có thể từ nguồn đến đích với chính xác k cạnh trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm số lần đi bộ từ nguồn đến đích với chính xác k cạnh.

Đối với điều này, chúng tôi sẽ được cung cấp với một biểu đồ và các giá trị của nguồn và đích. Nhiệm vụ của chúng tôi là tìm tất cả các đường có thể bắt đầu từ nguồn đến đích có chính xác k cạnh.

Ví dụ

#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;
}

Đầu ra

2