《图的深度广度遍历和最短路径问题(迪杰斯特拉算法实现)(共23页).doc》由会员分享，可在线阅读，更多相关《图的深度广度遍历和最短路径问题(迪杰斯特拉算法实现)(共23页).doc（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上 实 验 报 告课程名称 数据结构 实验项目 图的深度广度遍历和最短路径 实验仪器 计算机 学生姓名 徐申毅 实验日期 2013-6-7 成 绩 实验1 一、实验目的理解图的深度和广度遍历，能利用迪杰斯特拉算法求出最短路径二、实验内容 编写能求解图的深度和广度遍历和最短路径的程序三、实验课时4课时四、 实验步骤（1） 利用邻接矩阵实现图的存储（2） 利用栈实现图的深度遍历（3） 利用队列实现图的广度遍历（4） 用迪杰斯特拉算法求图的最短路径（5） 编写主函数（6） 编译，调试，运行五、 实验心得本次实验让我学会了利用栈和队列的数据结构实现图的深度和广度遍历，能用迪杰斯
2、特拉算法求出无向网的最短路径。六、 程序运行结果截图以及C程序源代码#include #include #define INFINITY 65535#define MAXVEXNUM 20typedef struct ArcCellint adj; / int(VRType)是顶点关系类型。char *info; /该弧相关信息的指针ArcCell, AdjMatrixMAXVEXNUM MAXVEXNUM;typedef structchar vexsMAXVEXNUM4;AdjMatrix arcs;int vexnum,arcnum;MGraph;#define QUEUE_INIT_S
3、IZE 100#define QUEUEINCREMENT 10typedef int QElemType;typedef structQElemType *elem;int front;int rear;int queuesize;int incrementsize;SqQueue;#include #include void InitQueue_Sq(SqQueue *Q,int n)Q-elem=(QElemType *)malloc(QUEUE_INIT_SIZE+1)*sizeof(QElemType);Q-queuesize=n;Q-incrementsize=QUEUEINCRE
4、MENT;Q-front=Q-rear=0;int QueueLength_Sq(SqQueue Q)return(Q.rear-Q.front+Q.queuesize)%Q.queuesize;int DeQueue_Sq(SqQueue *Q,QElemType *e)if(Q-front=Q-rear) return 0;*e=Q-elemQ-front;Q-front=(Q-front+1)%Q-queuesize;return 1;void incrementQueuesize(SqQueue *Q)QElemType *a; int k;a=(QElemType *)malloc(
5、Q-queuesize+Q-incrementsize)*sizeof(QElemType);for(k=0;kqueuesize-1;k+)ak=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;void EnQueue_Sq(SqQueue *Q,QElemType e)if(Q-rear+1)%Q-queuesize=Q-front)incrementQueuesize(Q);Q-elemQ-rear=e;Q-re
6、ar=(Q-rear+1)%Q-queuesize;int GetQueue_Sq(SqQueue Q,QElemType *e)if(Q.front=Q.rear) return 0;*e=Q.elemQ.front;return 1;int QueueEmpty(SqQueue Q)if(Q.front=Q.rear) return 1;else return 0;int visitedMAXVEXNUM;int LocateVex(MGraph *G,char v4)int i=0; while(ivexnum )if(strcmp(G-vexsi,v)=0) return i; i+;
7、printf(n 输入的顶点不存在！);return 0;void DFS(MGraph *G,int i) int j; printf(%7s,G-vexsi); visitedi=1; for(j=0; jvexnum; j+) if( i!=j & G-arcsij.adj !=INFINITY & !visitedj)DFS(G,j); void DFSTraverse(MGraph *G)int i,j;char v4;for(i=0;ivexnum;i+)visitedi=0;printf(输入起始点Vi： );getchar();scanf(%s,v);j=LocateVex(G
8、,v);DFS(G,j);for(i=0;ivexnum;i+)if(!visitedi)DFS(G,i);void BFS(MGraph *G,int i)int k,j; SqQueue Q; InitQueue_Sq(&Q,G-vexnum); printf(%5s,G-vexsi); visitedi=1; EnQueue_Sq(&Q,i); while(!QueueEmpty(Q)DeQueue_Sq(&Q,&k); for(j=0; jvexnum; j+)if( k!=j & G-arcskj.adj !=INFINITY & !visitedj)printf(%5s,G-vex
9、sj); visitedj=1; EnQueue_Sq(&Q,j); void BFSTraverse(MGraph *G)int i,j;char v4;for(i=0;ivexnum;i+)visitedi=0;printf(输入广度优先搜索初始顶点Vi： );getchar();scanf(%s,v);j=LocateVex(G,v);BFS(G,j);for(i=0;ivexnum;i+)if(!visitedi)BFS(G,i);void CreateUDN(MGraph *G) int i,j,k,w;char v14,v24;printf(输入vexnum arcnum: );s
10、canf(%d%d,&G-vexnum,&G-arcnum);printf(输入vexsi: n);getchar();for(i=0; ivexnum; +i)gets(G-vexsi);for(i=0; ivexnum; +i)for(j=0; jvexnum; +j)if(i=j)G-arcsij.adj=0;elseG-arcsij.adj=INFINITY;G-arcsij.info=NULL; for(k=0; karcnum; +k)printf(输入v1 v2 w: );scanf(%s %s %d,v1,v2,&w);i=LocateVex(G,v1);j=LocateVex
11、(G,v2);printf(%4s%4s%8d%8dn,v1,v2,i,j);G-arcsij.adj=w;G-arcsji.adj =G-arcsij.adj;void CreateGraph(MGraph *G) CreateUDN(G);printf(图构建完毕!n);void shortesPath_DIJ( MGraph *G,int v0,int pMAXVEXNUM,int dMAXVEXNUM)int i,j, v, min, w, finalMAXVEXNUM, v1, w1;for(v=0; vvexnum; +v)finalv=0; /设置顶点已求得最短路径的标志都为0d
12、v=G-arcsv0v.adj ; /设置dv，表示从v0 到v 的权值for(w=0; wvexnum; +w) /设空路径pvw=0;if(dvINFINITY) /标记路径顶点pvv0=1; pvv=1;printf(nfinal: ); /打印各数据结构的初始状态，for(v1=0; v1vexnum; +v1)printf(%6d,finalv1);printf(nn d: );for(v1=0; v1vexnum; +v1)printf(%6d,dv1);printf(nnp:n);for(v1=0; v1vexnum; +v1)for(w1=0; w1vexnum; +w1)pr
13、intf(%6d,pv1w1);putchar(n);/开始主循环，每次求得v0（为起始顶点）到某个v 顶点的最短路径，并加到S 集/若finalvi为1 则表示vi 为属于已求得的最短路径的终点的集合s。dv0=0; finalv0=1; /初始化，v0 顶点属于s 集for(i=1; ivexnum; +i) /其余G-vexnum-1 个顶点min=INFINITY; /当前所知离v0 顶点的最近距离for(w=0; wvexnum; +w) /找权值最小的（最近的）if(!finalw) /w 顶点在V-S 中if(dwmin) /w 顶点离v0 顶点更近v=w; /最小权值的下标mi
14、n=dw; /min 最小权值finalv=1; /标记该顶或边已处理，即离v0 顶点最近的加入S 集for(w=0; wvexnum; +w) /更新当前最短路径及距离if(!finalw&(min+G-arcsvw.adjarcs vw.adj ; /w 属于V-Sfor(j=0; jvexnum; +j) /复制路径顶点标记pwj=pvj;pww=1;printf(nfinal: ); /打印中间结果，跟踪数据变化for(v1=0; v1vexnum; +v1)printf(%6d,finalv1);printf(nn d: );for(v1=0; v1vexnum; +v1)print
15、f(%6d,dv1);printf(nnp:n);for(v1=0; v1vexnum; +v1)for(w1=0; w1vexnum; +w1)printf(%6d,pv1w1);putchar(n);void main()MGraph G; int i,j; char v4,pd;int pMAXVEXNUMMAXVEXNUM,dMAXVEXNUM;CreateGraph(&G);for(i=0; iG.vexnum; +i) /打印邻接矩阵for(j=0; jG.vexnum; +j)printf(%8d,G.arcsij.adj);putchar(n);getchar();printf
16、(下面进行图的操作：n);printf(1-图的深度优先搜索，2-图的广度优先搜索n);printf(3-求单源最短路径,4-退出程序n);for(pd=getchar();pd!=4;printf(请输入你想进行的操作序号n),getchar(),pd=getchar()switch(pd)case 1:DFSTraverse(&G);putchar(n);break;/深度优先搜索case 2:BFSTraverse(&G);putchar(n);break;/广度优先搜索case 3: printf(下面开始求最短单源路径，请输入单源的源关键字n); getchar(); scanf(%s,v); i=LocateVex(&G,v); shortesPath_DIJ(&G,i,p,d); break;default:printf(Error!n);/专心-专注-专业