图的深度广度遍历和最短路径问题(迪杰斯特拉算法实现).doc

《图的深度广度遍历和最短路径问题(迪杰斯特拉算法实现).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告课程名称数据结构实验项目图的深度广度遍历和最短路径实验仪器计算机学生姓名徐申毅实验日期2013-6-7成绩实验1一 、实验目的理解图的深度和广度遍历，能利用迪杰斯特拉算法求出最短路径二、 实验内容编写能求解图的深度和广度遍历和最短路径的程序三、实验课时4课时共23页第22页四、实验步骤（1）利用邻接矩阵实现图的存储（2）利用栈实现图的深度遍历（3）利用队列实现图的广度遍历（4）用迪杰斯特拉算法求图的最短路径（5）编写主函数（6）编译，调试，运行五、实验心得本次实验让我学会了利用栈和队列的数据结

2、构实现图的深度和广度遍历，能用迪杰斯特拉算法求出无向网的最短路径。六、程序运行结果截图以及C程序源代码#include#include#defineINFINITY65535#defineMAXVEXNUM20typedefstructArcCell{intadj;//int(VRType)是顶点关系类型。char*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAXVEXNUM][MAXVEXNUM];typedefstruct{共23页

3、第22页charvexs[MAXVEXNUM][4];AdjMatrixarcs;intvexnum,arcnum;}MGraph;#defineQUEUE_INIT_SIZE100#defineQUEUEINCREMENT10typedefintQElemType;typedefstruct{QElemType*elem;intfront;intrear;intqueuesize;intincrementsize;}SqQueue;共23页第22页#include#include<

4、stdlib.h>voidInitQueue_Sq(SqQueue*Q,intn){Q->elem=(QElemType*)malloc((QUEUE_INIT_SIZE+1)*sizeof(QElemType));Q->queuesize=n;Q->incrementsize=QUEUEINCREMENT;Q->front=Q->rear=0;}intQueueLength_Sq(SqQueueQ){return(Q.rear-Q.front+Q.queuesize)%Q.queuesize;}in

5、tDeQueue_Sq(SqQueue*Q,QElemType*e){if(Q->front==Q->rear)return0;*e=Q->elem[Q->front];共23页第22页Q->front=(Q->front+1)%Q->queuesize;return1;}voidincrementQueuesize(SqQueue*Q){QElemType*a;intk;a=(QElemType*)malloc((Q->queuesize+Q->incrementsize)*sizeof(QElem

6、Type));for(k=0;kqueuesize-1;k++)a[k]=Q->elem[(Q->front+k)%Q->queuesize];free(Q->elem);Q->elem=a;Q->front=0;Q->rear=Q->queuesize-1;Q->queuesize+=Q->incrementsize;}voidEnQueue_Sq(SqQueue*Q,QElemTypee)共23页第22页{if((Q->rear+1)%Q->queuesize==Q->front)incr

7、ementQueuesize(Q);Q->elem[Q->rear]=e;Q->rear=(Q->rear+1)%Q->queuesize;}intGetQueue_Sq(SqQueueQ,QElemType*e){if(Q.front==Q.rear)return0;*e=Q.elem[Q.front];return1;}intQueueEmpty(SqQueueQ){if(Q.front==Q.rear)return1;共23页第22页elsereturn0;}intvisited[MAXVEXN

8、UM];intLocateVex(MGraph*G,charv[4]){inti=0;while(ivexnum){if(strcmp(G->vexs[i],v)==0)returni;i++;}printf("输入的顶点不存在！");return0;}voidDFS(MGraph*G,inti)共23页第22页{intj;printf("%7s",G->vexs[i]);visited[i]=1;for(j=0;jvexnum;j+