判断无向图两点间是否存在长度为K的路径
2018-07-03 01:00:34来源:博客园 阅读 ()
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【图论】几个例题~ 2020-04-14
- 加边的无向图--并查集 2020-04-10
- 标准输入重定向到文件后,如何连续读入,如何判断标准输入流 2020-03-20
- 位运算的应用 2020-02-13
- 判断一个非空单链表是否是递增有序的 2019-12-15
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash