//判断无向图G是否连通。若连通则返回1;否则返回0。(填空)提示:采用遍历方式判断无向图G是否连通。这里用dfs,先给visited[]数组置初值0,然后从0顶点开始遍历该图,之后,若所有顶点I的visited[I]均为1,则该图是连通的;否则不连通。
#以下是我的代码,有些些长,请有空的大佬帮查看一下 (*꒦ິ⌓꒦ີ) (*꒦ິ⌓꒦ີ),运行结果出现错误,有乱码,下方链接是运行结果的截图。
截图:
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define max 20
typedef struct arcnode
{
int adjvex;
struct arcnode *nextarc;
int weight;
}arcnode;
typedef struct Vexnode
{
int data;
arcnode *firstarc;
}adjlist[max];
typedef struct graphs
{
adjlist Adjlist;
int vexnum,arcnum;
}graph;
void create (graph *g)
{
int n,e,l,j,k;
arcnode *p;
printf("创建一个图:\t"); //\t水平制表符
printf("顶点数:");
scanf("%d",&n);
//getchar();
printf("\t边数:");
scanf("%d",&e);
g=(graph *)malloc(sizeof(graph));
g->vexnum=n;
g->arcnum=e;
for(l=0;l<n;l++)
{
g->Adjlist[l].data=l;
g->Adjlist[l].firstarc=NULL;
}
for(k=0;k<e;k++)
{
printf("第%d+条边(节点号从0到%d-1):\n",k,n);
scanf("%d,%d",&l,&j);
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex==j;
p->nextarc=g->Adjlist[l].firstarc;
g->Adjlist[l].firstarc=p;
}
}
void disp(graph *g)
{
int l,have;
arcnode *p;
printf("输出图:\n");
for(l=0;lvexnum;l++)
{
p=g->Adjlist[l].firstarc;
have=0;
while(p!=NULL)
{
printf("(%d,%d\n",l,p->adjvex);
p=p->nextarc;
have=1;
}
if(have==1)
printf("\n");
}
}
void dfs(graph g,int v,int visited[])
{
arcnode *p;
printf("%d\n",v);
visited[v]=1;
p=g.Adjlist[v].firstarc;
while(p!=NULL)
{
if(!visited[p->adjvex])
dfs(g,p->adjvex,visited);
p=p->nextarc;
}
}
graph creatng()
{
int n=4,e=10,l,j,k;
graph g;
arcnode *p;
int edge[][2]={{0,3},{3,0},{0,1},{1,0},{1,2},{2,1},{2,3},{3,2},{0,2},{2,0}};
g.vexnum=n;g.arcnum=e;
for(l=0;l<n;l++)
{
g.Adjlist[l].data=l;
g.Adjlist[l].firstarc=NULL;
}
for(k=0;k<e;k++)
{
l=edge[k][0];
j=edge[k][1];
p=(arcnode *)malloc(sizeof(arcnode));
p->nextarc=g.Adjlist[l].firstarc;
g.Adjlist[l].firstarc=p;
}
return g;
}
int connect(graph g)
{
int l,flag=1;
int visited[20];
for(l=0;l<g.vexnum;l++)
{
visited[l]=0;
dfs(g,0,visited);
}
for(l=0;l<g.vexnum;l++)
if(visited[l]==0)
{
flag=0;
break;
}
return flag;
}
int main()
{
graph g;
g=creatng();
disp(&g);
printf("深度优先搜素顺序:\n");
if(connect(g)==1)
printf("为连通图\n");
else
printf("不为连通图\n");
//printf("(connect(g)==1 ? "该连通图":"该图不连通")\n");
system("pause");
return 0;
}