| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 879 人关注过本帖
标题:我想了两天了,还是没有头绪,无向图寻找所有路径的问题
只看楼主 加入收藏
火蚂
Rank: 1
等 级:新手上路
帖 子:26
专家分:0
注 册:2006-5-19
收藏
 问题点数:0 回复次数:4 
我想了两天了,还是没有头绪,无向图寻找所有路径的问题
图片附件: 游客没有浏览图片的权限,请 登录注册

如图所示,要求找到从1到6的所有路径
我在程序里面构造了一个无向图,一个栈
不知道使用循环还是用递归来控制栈,使得可行路径保存在栈中
输出格式如下:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
帮忙想一想,万分感谢……

搜索更多相关主题的帖子: 头绪 路径 
2007-05-13 19:22
火蚂
Rank: 1
等 级:新手上路
帖 子:26
专家分:0
注 册:2006-5-19
收藏
得分:0 
希望帮我想想算法,我在线等的
主要是判断什么条件入栈,什么条件出栈,什么条件退出循环或者怎么使用递归等等,谢谢大家了
2007-05-13 20:38
火蚂
Rank: 1
等 级:新手上路
帖 子:26
专家分:0
注 册:2006-5-19
收藏
得分:0 
帮忙啊,数据结构高手们赐教好吗,不能让这个帖子沉底啊,谢谢了,叩首!
2007-05-13 20:58
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 

程序代码:

#include <iostream>

using namespace std;

int adjmatrix[6][6]={
{0,1,1,0,0,0},
{1,0,1,1,0,0},
{1,1,0,1,1,0},
{0,1,1,0,0,1},
{0,0,1,0,0,1},
{0,0,0,1,1,0},
};

int x[6],used[6];

void dfs(int v)
{
if(x[v-1]==5){
printf(\"%d\",x[0]+1);
for(int i=1;i<v;i++){
printf(\" %d\",x[i]+1);
}
printf(\"\n\");
}
else {
for(int i=0;i<6;i++){
if(adjmatrix[x[v-1]][i]==1 && used[i]==0){
used[i]=1;
x[v]=i;
dfs(v+1);
used[i]=0;
}
}
}
}

int main()
{
x[0]=0;
used[0]=1;
dfs(1);
system(\"pause\");
}

2007-05-14 22:43
herbert_1987
Rank: 5Rank: 5
等 级:贵宾
威 望:15
帖 子:1314
专家分:0
注 册:2007-5-13
收藏
得分:0 

用广度优先搜索应该可以吧


人生重要的不是所站的位置,而是所朝的方向
2007-05-16 02:09
快速回复:我想了两天了,还是没有头绪,无向图寻找所有路径的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.032504 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved