数据结构实验七图的创建与遍历.doc

《数据结构实验七图的创建与遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验七图的创建与遍历实验目的：通过上机实验进一步掌握图的存储结构及基本操作的实现。实验内容与要求：要求：⑴能根据输入的顶点、边/弧的信息建立图；⑵实现图中顶点、边/弧的插入、删除；⑶实现对该图的深度优先遍历；⑷实现对该图的广度优先遍历。备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。算法设计：3#include#include#defineINFINITY32767#defineMAX_VEX20//最大顶点个数#defineQUEUE_SIZE(MAX_VEX+1)//队列长度usingnamesp

2、acestd;bool*visited;//访问标志数组//图的邻接矩阵存储结构typedefstruct{char*vexs;//顶点向量intarcs[MAX_VEX][MAX_VEX];//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}Graph;//队列类classQueue{public:voidInitQueue(){base=(int*)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;}voidEnQueue(inte){base[rear]=e;rear=(rear+1)%Q

3、UEUE_SIZE;}voidDeQueue(int&e){e=base[front];front=(front+1)%QUEUE_SIZE;}public:int*base;intfront;intrear;};//图G中查找元素c的位置intLocate(GraphG,charc){for(inti=0;i

4、");scanf("%d%d",&G.vexnum,&G.arcnum);temp=getchar();//接收回车G.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配顶点数目printf("输入%d个顶点.",G.vexnum);for(i=0;i

5、G.vexnum;j++)G.arcs[i][j]=INFINITY;printf("输入%d条弧.",G.arcnum);for(i=0;i

6、if(k>=0&&k=0&&i=0&&j

7、aphG,intk)//深度优先遍历{inti;if(k==-1)//第一次执行DFS时,k为-1{for(i=0;i=0;i=NextVex(G,k,i))if(!visited[i])DFS(G,i);//对k的尚未访问的邻接顶点i递归调用DFS}}voidBFS(GraphG)//广度优先遍历

8、{intk;QueueQ;//辅助队列QQ.InitQueue();for(inti=0;i<