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

1、实验项目名称：图的遍历一、实验目的应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。二、实验内容问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印由用邻接表或邻接矩阵表示的图的储存结构。三、实验仪器与设备计算机，Code:Blocks。四、实验原理用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索,并输由遍历的结果。五、实验程序及结果#defineINFINITY10000/*无穷大*/#defineMAX_VERTEX_NUM40#defineMAX40#include#include#include

2、#includetypedefstructArCellintadj;ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructcharname20;infotype;typedefstructinfotypevexsMAX_VERTEX_NUM;AdjMatrixarcs;intvexnum,arcnum;MGraph;intLocateVex(MGraph*G,char*v)intc=-1,i;for(i=0;ivexnum;i+)if(strcmp(v,G-)=0)c=i;break;returnc;MGraph

3、*CreatUDN(MGraph*G)/初始化图，接受用户输入inti,j,k,w;charv120,v220;printf(请输入图的顶点数，弧数:);scanf(%d%d,&G-vexnum,&G-arcnum);printf(结点名字:n);for(i=0;ivexnum;i+)printf(No.%d:,i+1);scanf(%s”,G-);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;printf(请输入一条边依附的两个顶点和权值:n);for(k=0;karcnum;k+)printf(第

4、d条边:n,k+1);printf(起始结点:);scanf(%s,v1);printf(结束结点:);scanf(%s,v2);/printf(边的权值:);/scanf(%d,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i=0&j=0)/G-arcsij.adj=w;G-arcs皿i=G-arcs皿;returnG;intFirstAdjVex(MGraph*G,intv)(inti;if(v=0&vvexnum)/v合理for(i=0;ivexnum;i+)if(G-arcsvi.adj!=INFINITY)returni;return-1;vo

5、idVisitFunc(MGraph*G,intv)printf(%s,G-);intNextAdjVex(MGraph*G,intv,intw)intk;if(v=0&vvexnum&w=0&wvexnum)/v,w合理for(k=w+1;kvexnum;k+)if(G-arcsvk.adj!=INFINITY)returnk;return-1;)intvisitedMAX;voidDFS(MGraph*G,intv)/从第v个顶点出发递归地深度优先遍历图G(intw;visitedv=1;VisitFunc(G,v);/访问第v个结点for(w=FirstAdjVex(

6、G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);printf(%d”,G-arcsvw);)voidDFSTraverse(MGraph*G,char*s)深度优先遍历intv,k;for(v=0;vvexnum;v+)visitedv=0;k=LocateVex(G,s);if(k=0&kvexnum)for(v=k;v=0;v-)if(!visitedv)DFS(G,v);for(v=k+1;vvexnum;v+)if(!visitedv)DFS(G,v);typedefstructQnodeintvexnum;structQnode*n

7、ext;QNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;LinkQueue;intInitQueue(LinkQueue*Q)Q-front=Q-rear=(QueuePtr)malloc(sizeof(QNode);if(!Q-front)exit(0);Q-front-next=NULL;return1;voidEnQueue(LinkQueue*Q,inta)QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(0);p-vexnum=a;p-next=NULL;Q-re

8、ar-next=p;Q-rear=p;intDeQueue(LinkQueue*Q,int*v)QueuePtrp;if(Q-front=Q-rear)printf(结点不存在!n);exit(0);p=Q-front-next;*v=p-vexnum;Q-front-next=p-next;if(Q-rear=p)Q-front=Q-rear;return*v;intQueueEmpty(LinkQueue*Q)if(Q-rear=Q-front)return0;return1;)intVisitedMAX;voidBFSTraverse(MGraph*G,char*str)/广度优先遍历i

9、ntw,u,v,k;LinkQueueQ,q;for(v=0;vvexnum;v+)Visitedv=0;InitQueue(&Q);InitQueue(&q);k=LocateVex(G,str);for(v=k;v=0;v-)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v入队while(!QueueEmpty(&Q)DeQueue(&Q,&u);/出队for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)if(!Visitedw)Visitedw=1;VisitFunc(G,v);EnQu

10、eue(&Q,w);)for(v=k+1;vvexnum;v+)if(!Visitedv)Visitedv=1;VisitFunc(G,v);EnQueue(&Q,v);/v入队while(!QueueEmpty(&Q)DeQueue(&Q,&u);/出队for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w)if(!Visitedw)Visitedw=1;VisitFunc(G,v);EnQueue(&Q,w);)voidmain()(MGraph*G,b;charv10;G=CreatUDN(&b);printf(请输入起始结点名称:);scanf(%s,v);printf(n深度优先遍历:n);DFSTraverse(G,v);printf(n广度优先遍历:n);BFSTraverse(G,v);getch();)六、实验总结实验要求输入图中节点的个数和边的个数，能够打印由用邻接表或邻接矩阵表示的图的储存结构。在设计中其中用邻接表表示的节点的值只能是数字，但用邻接矩阵表示的节点的值可以是字母。但用邻接表形式要相对简单一些。深度优先采取的递归思想。首先，将从起点，沿某条边，顺势遍历下去，直到不能继续遍历下去。这时，又从起点的另一结点开始，遍历下去。如