判断无向图是否为连通图

剑麟 发布于 2012/05/30 21:28
阅读 5K+
收藏 1
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
#define VertexType int

typedef struct node
{
int adjvex;
struct node *next;
}EdgeNode;

typedef struct vnode
{
VertexType vertex;
EdgeNode *firstedge;
}VertexNode;

VertexNode AdjList[MAXSIZE];
int flag[MAXSIZE];
int N,E;
int count=0;             //定义为全局变量

void create_Graph(VertexNode AdjList[])
{
int i,j,k;
EdgeNode *s;
printf("输入图的顶点数和边数:");
scanf("%d %d",&N,&E);

printf("按序号顺序输入顶点的信息(空格相间输入):");
for(i=0;i<N;i++)
{
scanf("%d",&AdjList[i].vertex);
AdjList[i].firstedge=NULL;
}

printf("输入边的集合(vi,vj)偶对\n");
for(k=0;k<E;k++)
{
printf("输入第%d条边两端顶点的序号:",k+1);
scanf("%d %d",&i,&j);
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=j;
s->next=(AdjList[i]).firstedge;
AdjList[i].firstedge=s;
}
}

void DFS(VertexNode AdjList[], int i)
{
int j;
EdgeNode *p;
printf("%d_",AdjList[i].vertex);
flag[i]=1;
p=AdjList[i].firstedge;
while(p)
{
j=p->adjvex;  //取出firstedge的序号。
if(!flag[i])
DFS(AdjList,j);
p=p->next;
}
}

void DFSTraverseAl(VertexNode AdjList[])
{
int i;
//printf("输入开始访问的结点的序号:");
//scanf("%d",&s);
for(i=0;i<N;i++)
flag[i]=0;

for(i=0;i<N;i++)
{
if(!flag[i])
{
DFS(AdjList,i);
count++;         
}
}
}


void main()
{
create_Graph(AdjList);
printf("DFS遍历结果如下\n");
DFSTraverseAl(AdjList);
printf("\n");
if(count>1)
printf("你所创建的图不是连通图\n");
else
printf("你所创建的图是连通图\n");
}

以下是问题补充:

@剑麟:书本的算法里不是说在DFSTraverseAl函数中的for循环中设置个count变量,当count变量大于1时,该图就为连通图吗?怎么就不行呢?高手帮帮忙 (2012/05/30 21:30)
@剑麟:@中山野鬼 @红薯 @疯疯 @李勇2 @水牛叔叔 @周翼翼 (2012/05/30 21:46)
@剑麟:j=p->adjvex; //取出firstedge的序号。 if(!flag[i]) 这里的 flag[i] 修改为 flag[j]. (2012/05/30 23:08)
加载中
1
中山野鬼
中山野鬼

简单看一下,你下面的代码是不是敲错了

j=p->adjvex;  //取出firstedge的序号。
if(!flag[i])
DFS(AdjList,j);
p=p->next;
应该是
if (!flag[j])吧。
剑麟
剑麟
诶,果然,我再试试
0
m2012
m2012
大于1的时候不是连通图。
剑麟
剑麟
可是我调试发现count无论怎样总是等于N,无论是否为连通图,还是我测试错了
0
m2012
m2012
是的,楼主,你的程序打错了
0
中山野鬼
中山野鬼
另外,我没收到你CALL我的信息。哈。。得问下@红薯 怎么回事。
中山野鬼
中山野鬼
回复 @剑麟 : 难道看到一个美女和她套近乎就是为了上她吗?或者一定能上的美女你才套近乎吗????这种美女观,很肤浅!!!!
剑麟
剑麟
其实图的连通性判断在实际编程应用中用处大不大的?本人还是大一的学生,对它的实用性不了解
中山野鬼
中山野鬼
回复 @剑麟 : 图还难啊 ????无语了。。哈。。。
剑麟
剑麟
回复 @中山野鬼 : 那假如用我现在写的那个程序,那个count的值什么时候是连通图,什么时候不是联通图?唉,烦恼啊,弄了几天都没搞定,感觉图很难学啊
中山野鬼
中山野鬼
回复 @剑麟 : 哈。理论上的算法都一样。只不过工程优化有不一样的东西。但和你没有关系。原理性的设计,保证正确性就可以了。
下一页
0
撸红薯
撸红薯
并查集是最好的办法。我觉得
撸红薯
撸红薯
回复 @剑麟 : 一个算法,百度下吧!很简单的。速度也是不错的!!
剑麟
剑麟
什么是“并查集”?
返回顶部
顶部