实验三 图的存储结构及各种运算的实现

《实验三 图的存储结构及各种运算的实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三图的存储结构及各种运算的实现（必做）计算机与信息技术学院14级3班黄雨梅201421012808计算机科学与技术实验目的：   1、掌握图的逻辑结构及其常用的存储表示方法，建立图的邻接表与邻接矩阵。2、熟练掌握图的深度与广度优先搜索算法的基本思想，并能在不同存储结构上实现算法。3、深入理解最小生成树的定义，掌握Prim算法和Kruskar算法构造最小生成树的基本思想，并实现Prim算法。4、掌握用DIJKSTTRA算法求解单源最短路径的基本过程和算法。实验学时:8实验内容：1、建立图的邻接表与邻接矩阵，并在不同

2、存储结构上实现深度与广度优先搜索算法。   2、用Prim算法构造带权网络的最小生成树。   3、用DIJKSTTRA算法求解单源最短路径。 选做部分4、求拓朴序列和关键路径。第一题：建立图的邻接表与邻接矩阵，并在不同存储结构上实现深度与广度优先搜索算法#include#include#defineINFINITY32767#defineMAX_VEX20#defineQUEUE_SIZE(MAX_VEX+1)bool*visited;typedefstruct{char*vex

3、s;//顶点向量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)%QUEUE_SIZE;}voidDeQueue(int&e){e=base[front];

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

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

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

7、hG,intk){if(k>=0&&k=0&&i=0&&j

8、nk;return-1;}//深度优先遍历voidDFS(GraphG,intk){inti;if(k==-1)//第一次执行DFS时,k为-1{for(i=0;i