| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 602 人关注过本帖
标题:请大家看一下这个关于图的回路问题
只看楼主 加入收藏
蓝色雨
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2006-5-22
收藏
 问题点数:0 回复次数:0 
请大家看一下这个关于图的回路问题

这是一个关于图的问题,请大家帮我看看错在哪里,帮忙改一下,谢谢`。。
#include<iostream.h>
#include<bitset>
using namespace std;
#define MAX 50
int n;
bool dfs(int a[][MAX],int x,int d,bitset<MAX> &visited)
{
if(d==n-1)
{
cout<<"能够找到一条连接所有边的简单路径:"<<endl;
cout<<x+1<<' ';
return true;
}
visited[x]=1;
for(int i=0;i<n;i++)
{
if(a[x][i]>0 && visited[i]==0)
{
if( dfs(a,i,d+1,visited) )
{
cout<<"->"<<x+1;
return true;
}
}
}
visited[x]=0;
return false;
}

bool dfs_bool_can(int a[][MAX],int x,const int &end,bitset<MAX> &visited)
{
if(x==end)
{
cout<<"能够找到一条连接这两个顶点的简单路径:"<<endl;
cout<<x+1<<' ';
return true;
}
visited[x]=1;
for(int i=0;i<n;i++)
{
if(a[x][i]>0 && visited[i]==0)
{
if( dfs_bool_can(a,i,end,visited) )
{
cout<<"->"<<x+1;
return true;
}
}
}
visited[x]=0;
return false;
}

int main()
{
// freopen("d:\\zny.in","r",stdin);
int a[MAX][MAX]; //a[i][j]<=0表示i和j没有边
cout<<"输入顶点的数目";
cin>>n;
cout<<"输入邻接矩阵";
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cin>>a[i][j];
}
for(i=0;i<n;i++) //从不同的点开始搜索;
{
bitset<MAX> visited(0);
if( dfs(a,i,0,visited) )
{
cout<<endl;
break;
}
}
if(i>=n) cout<<"没有找到这样一条路径"<<endl;

cout<<endl<<endl;

cout<<"输入想判断是否连通的两个顶点:";
int s,t;
cin>>s>>t;

bitset<MAX> visited(0);
if( dfs_bool_can(a,s-1,t-1,visited) )
{
cout<<endl;
}
else cout<<"没有找到能够连接"<<s<<"和"<<t<<"的一条路径"<<endl;

return 1;
}

搜索更多相关主题的帖子: 回路 dfs visited 
2006-06-27 07:27
快速回复:请大家看一下这个关于图的回路问题
数据加载中...
 
   



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

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