大大怪的一亩三分地 2021-12-04 16:03 采纳率: 100%
浏览 96
已结题

判断无向图是否为连通图,采用优先深度遍历方式(DFS)

//判断无向图G是否连通。若连通则返回1;否则返回0。(填空)提示:采用遍历方式判断无向图G是否连通。这里用dfs,先给visited[]数组置初值0,然后从0顶点开始遍历该图,之后,若所有顶点I的visited[I]均为1,则该图是连通的;否则不连通。
#以下是我的代码,有些些长,请有空的大佬帮查看一下 (*꒦ິ⌓꒦ີ) (*꒦ິ⌓꒦ີ),运行结果出现错误,有乱码,下方链接是运行结果的截图。
截图:

img

#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;
}

  • 写回答

0条回答 默认 最新

    报告相同问题?

    问题事件

    • 系统已结题 12月12日
    • 创建了问题 12月4日

    悬赏问题

    • ¥100 需要跳转番茄畅听app的adb命令
    • ¥50 寻找一位有逆向游戏盾sdk 应用程序经验的技术
    • ¥15 请问有用MZmine处理 “Waters SYNAPT G2-Si QTOF质谱仪在MSE模式下采集的非靶向数据” 的分析教程吗
    • ¥50 opencv4nodejs 如何安装
    • ¥15 adb push异常 adb: error: 1409-byte write failed: Invalid argument
    • ¥15 nginx反向代理获取ip,java获取真实ip
    • ¥15 eda:门禁系统设计
    • ¥50 如何使用js去调用vscode-js-debugger的方法去调试网页
    • ¥15 376.1电表主站通信协议下发指令全被否认问题
    • ¥15 物体双站RCS和其组成阵列后的双站RCS关系验证