欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

判断无向图两点间是否存在长度为K的路径

程序员文章站 2022-03-09 23:41:09
1 #include 2 #include 3 #define MAXN 5 4 using namespace std; 5 6 struct edge 7 { 8 int f,t; 9 edge(int f, int t) :f(f), t(t) {} 10 }; 11 12 vector ed... ......
 1 #include <iostream>
 2 #include <vector>
 3 #define MAXN  5
 4 using namespace std;
 5 
 6 struct edge
 7 {
 8     int f,t;
 9     edge(int f, int t) :f(f), t(t) {}
10 };
11 
12 vector<edge> edges;
13 vector<int> G[MAXN+1];
14 bool vis[MAXN+1];
15 
16 void init(){
17     for (int i = 1; i <= MAXN; i++)
18         vis[i] = false;
19 }
20 
21 
22 //通过缩短路径方法求解
23 bool search_k_path(int begin,int end,int k){
24     if(begin==end && k==0) return true;
25     //当要求的K大于 i 到 j 的长度,当 I ==J 时,k<0
26     if(k>0){
27         vis[begin] = true;
28         for(int i=0;i<G[begin].size();i++){
29             if(!vis[edges[G[begin][i]].t]) 
30                 return search_k_path(edges[G[begin][i]].t,end,k-1);
31         }
32         vis[begin] = false;
33     }
34     return false;
35 }
36 
37 
38 
39 int main(int argc, char const *argv[])
40 {
41     //input data
42 
43     int s,e;
44     for(int i= 0 ;i<7;i++){
45         cin>>s>>e;
46         edges.push_back(edge(s,e));
47         G[s].push_back(edges.size()-1);
48         edges.push_back(edge(e,s));
49         G[e].push_back(edges.size()-1);
50     }    
51     init();
52     cout <<search_k_path(1,5,2)<<endl;
53 
54     return 0;
55 }