两顶点的路径长度为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 
    
     using namespace std;//Make a pair between vertex x and vertex yvoid addedge(list
     
      *ls,int x,int y){
   	ls[x].push_back(y);	ls[y].push_back(x);}//count the number of paths existsvoid path_count(list
      
       *ls,int s,int d,bool *visit,int &count){
   	visit[s]=true;	if(s==d){
   		count++;	}	else{
   		list
       
        ::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
        
          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 : "<
         
          <
         
        
       
      
     
    

Output

输出量

Paths are : 4

翻译自:

两顶点的路径长度为k