兩頂點的路徑長度為k

What to Learn?

學什么？

How to count all possible paths between two vertices?

如何計算兩個頂點之間的所有可能路徑？

In the graph there are many alternative paths from vertex 0 to vertex 4

在圖中，有許多從頂點0到頂點4的替代路徑。

    1.	0 → 1 → 2 → 3 → 4
2.	0 → 1 → 4
3.	0 → 3 → 2 → 1 → 4
4.	0 → 3 → 4

Algorithm:

算法：

Here we use a recursive method to detect all the paths of a graph,

在這里，我們使用遞歸方法來檢測圖的所有路徑 ，

1. We start the recursive function with the starting vertex.

   我們從起始頂點開始遞歸函數。

2. For each node

   對于每個節點

   1. Whenever we visited one vertex we mark it and go for all its unvisited adjacent nodes.
   2. If we found the destination vertex then count the number else we go for recursive call.

    Check(current node){
visit[curr_node]=true;
if(curr_node == destination){
count++;
}
else{
for( all the adjacent vertices ){
if(not visited yet) then
check(adjacent vertex);
}
}
}

C++ implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
//Make a pair between vertex x and vertex y
void addedge(list<int>*ls,int x,int y){
ls[x].push_back(y);
ls[y].push_back(x);
}
//count the number of paths exists
void path_count(list<int>*ls,int s,int d,bool *visit,int &count){
visit[s]=true;
if(s==d){
count++;
}
else{
list<int>::iterator it;
for(it=ls[s].begin();it!=ls[s].end();it++){
if(!visit[*it]){
path_count(ls,*it,d,visit,count);
}
}
}
visit[s]=false;
}
int main()
{
list<int> ls[6];
addedge(ls,0,1);
addedge(ls,2,3);
addedge(ls,3,4);
addedge(ls,4,5);
addedge(ls,1,2);
addedge(ls,1,4);
addedge(ls,3,0);
bool visit[6];
for(int i=0;i<6;i++){
visit[i]=false;
}
int count=0;
path_count(ls,0,4,visit,count);
cout<<"Paths are : "<<count<<endl;
return 0;
}

Output

輸出量

Paths are : 4

翻譯自: https://www.includehelp.com/data-structure-tutorial/count-all-the-possible-path-between-two-vertices.aspx

兩頂點的路徑長度為k