图的遍历2 数据结构试验报告

本文格式为Word版，下载可任意编辑——图的遍历2数据结构试验报告

图的遍历

南昌航空大学试验报告

课程名称：数据结构试验名称：试验八图的遍历班级：学生姓名：学号：指导教师评定：签名:

题目：假设无向图采用邻接表结构表示。编程分别实现图的深度优先探寻算法

和广度优先探寻算法。一、需求分析

1.用户可以根据自己的需求进行输入所需的图（可以是非连通图也可以是连通图），其中1

表示创立一个有向图，2表示创立一个无向图。

2.用户进入菜单页面选择输入图的状态（1表示创立一个有向图，2表示创立一个无向图，

3表示输出已创立的图，4表示深度优先遍历已有的图，5表示广度优先遍历已有的图，6表示退出程序状态）。3.程序执行的命令包括：

（1）输入图的结点和弧构造图（2）输出图（2）广度优先遍历图（3）深度优先遍历图

二、概要设计

⒈为实现上述算法，需要链表的抽象数据类型：ADTGraph{

数据对象V：V是具有一致特征的数据元素的集合，称为顶点集。数据关系R：R={VR}

VR={v,w|v,w∈V且P（v,w），v,w表示从x到w的弧，谓词P（v,w）定义了弧

v,w的意义或信息}

基本操作P:

Creatgraph(G,V,VR)

初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。destroygraph(G)初始条件：图G存在。操作结果：销毁图G。displaygraph（G）初始条件：图G存在。操作结果：显示图G。locatevex(G,u)

初始条件：图G存在，u和G中的顶点有一致的特征。

操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回

图的遍历

其他信息。

getvex(G,v)

初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的值。DFStraverse(G)

初始条件：图G存在。

操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点访问一

次。

BFStraverse(S,e)

初始条件：图G存在。

操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点访问一

次。

}ADTGraph

2.本程序有三个模块：

⑴主程序模块

main(){初始化；

Switch（参数）{

Case1：接受命令（用户创立一个有向图）；Case2：接受命令（用户创立一个无向图）；Case3：接受命令（输出已创立的图）；

Case4：接受命令（深度优先遍历已有的图）；Case5：接受命令（广度优先遍历已有的图）；Case6：接受命令（退出程序）；｝｝⑵创立图的模块：主要建立一个图；

⑶广度优先遍历和深度优先遍历模块：输出这两种遍历的结果；(4)输出图模块：显示已创立的图。

三、详细设计

⒈元素类型，结点类型structarcnode

{intadjvex;/*该弧所指向的顶点的位置*/intinfo;

structarcnode*nextarc;/*指向下一条弧的指针*/};

structvexnode

{intdata;/*顶点的信息*/

structarcnode*firstarc;/*指向第一条依附该顶点的弧的指针*/};

structgraph

{structvexnode*vexpex;

intvexnum,arcnum;/*图的当前的顶点数和弧数*/}；

图的遍历

/*定义队列*/structqueue{

int*elem;intfront;intrear;};

/*全局变量*/

intn;/*图的顶点数*/

intvisit[100];/*标志数组*/structqueueQ;

2.对抽象数据类型中的部分基本操作的伪码算法如下：/*创立一个空队列*/

structqueueinitqueue(){structqueueq;

q.elem=(int*)malloc(maxsize*sizeof(int));if(!q.elem)exit(0);q.front=q.rear=0;returnq;}

/*入队列*/

structqueueenqueue(structqueueq,intv){if((q.rear+1)%maxsize==q.front)printf(thequeueisfull！！！\n);else

{q.elem[q.rear]=v;

q.rear=(q.rear+1)%maxsize;}

returnq;}

/*出队列*/

intdequeue(structqueueq){intcur;

if(q.rear==q.front)

{printf(thequeueisnull!!\n);exit(0);}else

{cur=q.elem[q.front];

q.front=(q.front+1)%maxsize;returncur;}}

/*判断队列是否为空*/

图的遍历

intemptyqueue(structqueueq){if(q.front==q.rear)return1;else

return0;}

/*创立有向图*/

structgraphcreatgraph1(){inte,i,s,d;inta;

structgraphg;structarcnode*p;

printf(thenumberofvex(n)andarc(e):);scanf(%d%d,n,e);g.vexnum=n;g.arcnum=e;

for(i=0;ig.vexnum;i++)

{printf(di%dvex'sinformation:,i);scanf(%d,a);g.vexpex[i].data=a;

g.vexpex[i].firstarc=NULL;}

for(i=0;ig.arcnum;i++)

{printf(di%darc'sstart,end:,i+1);scanf(%d%d,s,d);

p=(structarcnode*)malloc(sizeof(structarcnode));p-adjvex=d;

p-info=g.vexpex[d].data;

p-nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;}

returng;}

/*创立无向图*/

structgraphcreatgraph2(){inte,i,s,d;inta;

structgraphg;

structarcnode*p,*q;

printf(thenumberofvex(n)andarc(e):);scanf(%d%d,n,e);g.vexnum=n;g.arcnum=e;

for(i=0;ig.vexnum;i++)

图的遍历

{printf(di%dvex'sinformation:,i);scanf(%d,a);g.vexpex[i].data=a;

g.vexpex[i].firstarc=NULL;}

for(i=0;ig.arcnum;i++)

{printf(di%darc'sstart,end:,i+1);scanf(%d%d,s,d);

p=(structarcnode*)malloc(sizeof(structarcnode));p-adjvex=d;

p-info=g.vexpex[d].data;

p-nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;

q=(structarcnode*)malloc(sizeof(structarcnode));q-adjvex=s;

q-info=g.vexpex[s].data;

q-nextarc=g.vexpex[d].firstarc;g.vexpex[d].firstarc=q;}

returng;}

/*显示有向图*/

voiddisplaygraph(structgraphg,intn){inti;

structarcnode*p;

printf(diaplaythegraph;\n);for(i=0;in;i++)

{printf([%d,%d]-,i,g.vexpex[i].data);p=g.vexpex[i].firstarc;while(p!=NULL)

{printf((%d,%d)-,p-adjvex,p-info);p=p-nextarc;}

printf(^\n);}}

/*连通图广度优先遍历*/

voidBFSsearch(structgraphg,intv){inti;

structarcnode*p;Q=initqueue();

printf(%5d,g.vexpex[v].data);enqueue(Q,v);visit[v]=TURE;while(!emptyqueue(Q))

图的遍历

{i=dequeue(Q);

p=g.vexpex[i].firstarc;while(p!=NULL)

{enqueue(Q,p-adjvex);

if(visit[p-adjvex]==FALSE){

printf(%5d,p-info);visit[p-adjvex]=TURE;}

p=p-nextarc;}}}

/*非连通图广度优先遍历*/voidBFS(structgraphg)

{inti;printf(BFSresult:\n);for(i=0;ig.vexnum;i++)visit[i]=FALSE;

for(i=0;ig.vexnum;i++)if(visit[i]==FALSE)BFSsearch(g,i);printf(\n\n);}

/*连通图深度优先遍历*/

voidDFSsearch(structgraphg,intv){structarcnode*p;

printf(%5d,g.vexpex[v].data);visit[v]=TURE;p=g.vexpex[v].firstarc;while(p!=NULL)

{if(!visit[p-adjvex])DFSsearch(g,p-adjvex);p=p-nextarc;}}

/*非连通图深度优先遍历*/voidDFS(structgraphg)

{inti;printf(DFSresult:\n);

for(i=0;ig.vexnum;i++)visit[i]=FALSE;for(i=0;ig.vexnum;i++)

if(visit[i]==FALSE)DFSsearch(g,i);printf(\n\n);}

/*主菜单定义*/intmenu_select(){

图的遍历

chars[80];intc;

gotoxy(1,25);/*将光标定在第25行第1列*/

printf(pressanykeyentermenu\n);/*提醒按任意键继续*/getch();/*读入任意字符*/clrscr();/*清屏*/gotoxy(1,1);

printf(***************MENU***************\n\n);printf(1.Makeadigraphbyyouself!\n);printf(2.Makeaundigraphbyyouself!\n);printf(3.Ontputyourgraph!\n);

printf(4.Depth_firstsearchyourgraph!\n);printf(5.Bredth_firstsearchyourgraph!\n);printf(6.Quit!\n);

printf(**********************************\n);do{

printf(\nEnteryouchoice(1~6):\n);/*提醒输入选项*/scanf(%s,s);/*输入选择项*/

c=atoi(s);/*将输入的字符串转化为整型*/}while(c1||c6);returnc;}

3.主函数和其他函数的伪码算法voidmain()

{structgraphg;inti;

clrscr();/*清屏*/for(;;)

{switch(menu_select())

{case1:{clrscr();g=creatgraph1();break;}case2:{clrscr();g=creatgraph2();break;}case3:{clrscr();printf(diaplaythegraph;\n);displaygraph(g,n);break;}

case4:{clrscr();printf(DFSresult:\n);DFS(g);break;}

case5:{clrscr();printf(BFSresult:\n);BFS(g);break;}

case6:exit(0);}}}

图的遍历

4函数调用关系

main

initqueuedequeueenqueue

四、调试分析

⒈本来想将图的顶点元素的类型定义为字符型的，但是在运行的时候发现在输入顶点数和弧数后，总是会在有字符没有输入就直接运行下一个语句了，改变了好多的方法，最终只有将顶点的类型定义为才解决了上述的问题。⒉在写程序的时候，开始creatgraph函数的部分代码为for(i=0;ig.vexnum;i++)

{printf(di%dvex'sinformation:,i);scanf(%d,a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}

g.vexnum=n;g.arcnum=e;

总是会有这样的提醒“可能在‘g’定义以前已经使用了在creatgraph函数中〞，经过屡屡的调试，最终代码改为g.vexnum=n;g.arcnum=e;for(i=0;ig.vexnum;i++)

{printf(di%dvex'sinformation:,i);scanf(%d,a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}

就解决了问题，但是我还是不明白原因。

3.在编写BFSsearch函数的时候，用指针入队还是用下标值入队，由于对指针的把握不够，最终选择了比较简单的用下标值作为队列的类型int。

4.在调试的时候，选择选项3、4、5的时候总是没有执行printf语句，最终分别在主函数和要调用的函数中都加上同一printf语句就解决了问题，能够显示printf中的信息。5.算法的时空分析

各操作的算法时间繁杂度比较合理

initqueue，emptyqueue，enqueue，dequeue，visit为O(1)；creatgraph，displaygraph1，

图的遍历

displaygraph2BFSsearch，DFS，DFSsearch，BFS为O(n),注：n为图的顶点数。

6.本次试验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路明了，使调试也较顺利，各模块有较好的可重用性。

五、用户手册

⒈本程序的运行环境为windowsxp操作系统，并且在TC2.0中运行，执行文件为Exp8.c；⒉.在输入有向图的信息的时候，注意输入的顺序，这关系到顶点的位置，否则就会与你想

要的图就不一样了。如你的图为若你输入的顶点的顺序是20,18，21，22则它们对应的数值的下标为0,1,2，3。因此表示的弧（起点，终点）就应当为（0,2），（1,0），（2,1），（3,0），（3,2），但是弧输入的顺序没有要求。而创立无向图的时候就没有这个要求了，只要输入能表示该边的两个正确的端点即可。

3.按任意键进入主菜单如图：

注：1：表示创立一个有向图；

2：表示创立一个无向图；3：表示输出已创立的图；4：表示深度优先遍历已有的图；5：表示广度优先遍历已有的图；6：表示退出程序状态。

4.进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS环境中，用户根据需求键入相应的数据，可以看到相应的结果。

六、测试结果

若想创立一个无向图（在主菜单项选择择2）：

1912

则在主菜单项选择择2输入的图如下图：

图的遍历

按任意键进入主菜单项选择择3，输出图为：

按任意键进入主菜单项选择择4，输出DFS的结果：

按任意键进入主菜单项选择择5，输出BFS的结果

:

按任意键进入主菜单项选择择6，退出程序。

七、附录：源程序#includestdio.h#includemalloc.h#includestdlib.h#includestring.h#includectype.h#defineNULL0

图的遍历

#defineFALSE0#defineTURE1#definemaxsize100structarcnode

{intadjvex;/*该弧所指向的顶点的位置*/intinfo;

structarcnode*nextarc;/*指向下一条弧的指针*/};

structvexnode

{intdata;/*顶点的信息*/

structarcnode*firstarc;/*指向第一条依附该顶点的弧的指针*/};

structgraph

{structvexnode*vexpex;

intvexnum,arcnum;/*图的当前的顶点数和弧数*/};

/*定义队列*/structqueue{

int*elem;intfront;intrear;};

intn;/*图的顶点数*/

intvisit[100];/*标志数组*/structqueueQ;/*创立一个空队列*/

structqueueinitqueue(){structqueueq;

q.elem=(int*)malloc(maxsize*sizeof(int));if(!q.elem)exit(0);q.front=q.rear=0;returnq;}

/*入队列*/

structqueueenqueue(structqueueq,intv){if((q.rear+1)%maxsize==q.front)printf(thequeueisfull！！！\n);else

{q.elem[q.rear]=v;

q.rear=(q.rear+1)%maxsize;}returnq;}

/*出队列*/

图的遍历

intdequeue(structqueueq){intcur;

if(q.rear==q.front)

{printf(thequeueisnull!!\n);exit(0);}else

{cur=q.elem[q.front];

q.front=(q.front+1)%maxsize;returncur;}}

/*判断队列是否为空*/

intemptyqueue(structqueueq)

{if(q.front==q.rear)return1;elsereturn0;}

/*创立有向图*/

structgraphcreatgraph1()

{inte,i,s,d;inta;structgraphg;structarcnode*p;

printf(thenumberofvex(n)andarc(e):);scanf(%d%d,n,e);g.vexnum=n;g.arcnum=e;

for(i=0;ig.vexnum;i++)

{printf(di%dvex'sinformation:,i);scanf(%d,a);g.vexpex[i].data=a;

g.vexpex[i].firstarc=NULL;}

for(i=0;ig.arcnum;i++)

{printf(di%darc'sstart,end:,i+1);scanf(%d%d,s,d);

p=(structarcnode*)malloc(sizeof(structarcnode));p-adjvex=d;

p-info=g.vexpex[d].data;

p-nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;}

returng;}

/*创立无向图*/

structgraphcreatgraph2()

图的遍历

{inte,i,s,d;inta;structgraphg;structarcnode*p,*q;

printf(thenumberofvex(n)andarc(e):);scanf(%d%d,n,e);

g.vexnum=n;g.arcnum=e;for(i=0;ig.vexnum;i++)

{printf(di%dvex'sinformation:,i);scanf(%d,a);g.vexpex[i].data=a;

g.vexpex[i].firstarc=NULL;}

for(i=0;ig.arcnum;i++)

{printf(di%darc'sstart,end:,i+1);scanf(%d%d,s,d);

p=(structarcnode*)malloc(sizeof(structarcnode));p-adjvex=d;

p-info=g.vexpex[d].data;

p-nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;

q=(structarcnode*)malloc(sizeof(structarcnode));q-adjvex=s;

q-info=g.vexpex[s].data;

q-nextarc=g.vexpex[d].firstarc;g.vexpex[d].firstarc=q;}returng;}

/*显示图*/

voiddisplaygraph(structgraphg,intn){inti;structarcnode*p;printf(diaplaythegraph;\n);for(i=0;in;i++)

{printf([%d,%d]-,i,g.vexpex[i].data);p=g.vexpex[i].firstarc;while(p!=NULL)

{printf((%d,%d)-,p-adjvex,p-info);p=p-nextarc;}

printf(^\n);}}

/*连通图广度优先遍历*/

voidBFSsearch(structgraphg,intv){inti;structarcnode*p;Q=initqueue();

图的遍历

printf(%5d,g.vexpex[v].data);enqueue(Q,v);visit[v]=TURE;while(!emptyqueue(Q)){i=dequeue(Q);

p=g.vexpex[i].firstarc;while(p!=NULL)

{enqueue(Q,p-adjvex);

if(visit[p-adjvex]==FALSE){

printf(%5d,p-info);visit[p-adjvex]=TURE;}

p=p-nextarc;}}}

/*非连通图广度优先遍历*/voidBFS(structgraphg){inti;

printf(BFSresult:\n);for(i=0;ig.vexnum;i++)visit[i]=FALSE;

for(i=0;ig.vexnum;i++)if(visit[i]==FALSE)BFSsearch(g,i);printf(\n\n);}

/*连通图深度优先遍历*/

voidDFSsearch(structgraphg,intv){structarcnode*p;

printf(%5d,g.vexpex[v].data);visit[v]=TURE;p=g.vexpex[v].firstarc;while(p!=NULL)

{if(!visit[p-adjvex])DFSsearch(g,p-adjvex);p=p-nextarc;}}

voidDFS(structgraphg)/*非连通图深度优先遍历*/{inti;

printf(DFSresult:\n);for(i=0;ig.vexnum;i++)visit[i]=FALSE;

for(i=0;ig.vexnum;i