欢迎来到天天文库
浏览记录
ID:50959443
大小:60.50 KB
页数:3页
时间:2020-03-16
《数据结构实验七图的创建与遍历.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;i4、");scanf("%d%d",&G.vexnum,&G.arcnum);temp=getchar();//接收回车G.vexs=(char*)malloc(G.vexnum*sizeof(char));//分配顶点数目printf("输入%d个顶点.",G.vexnum);for(i=0;i5、G.vexnum;j++)G.arcs[i][j]=INFINITY;printf("输入%d条弧.",G.arcnum);for(i=0;i6、if(k>=0&&k=0&&i=0&&j7、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<
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;i5、G.vexnum;j++)G.arcs[i][j]=INFINITY;printf("输入%d条弧.",G.arcnum);for(i=0;i6、if(k>=0&&k=0&&i=0&&j7、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<
5、G.vexnum;j++)G.arcs[i][j]=INFINITY;printf("输入%d条弧.",G.arcnum);for(i=0;i6、if(k>=0&&k=0&&i=0&&j7、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<
6、if(k>=0&&k=0&&i=0&&j7、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<
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<
此文档下载收益归作者所有