数据结构实习三 图及其应用.doc

《数据结构实习三 图及其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构学院：姓名：班级：学号：实习三图及其应用题目：试设计一个算法，求图中一个源点到其他各顶点的最短路径。一.需求分析：设计要求：（1）用邻接表表示图；（2）按长度非递减次序打印输出最短路径的长度及相应路径。二.设计思想：本程序使用链表的形式存储的。根据书上的德克斯德拉算法的思想，初始状态时，集合s中只包含源点，设为v0，然后不断地从集合T中选择到源点v0路径长度最短的结点u加入到集合s中，集合s中每加入一个新的结点u都要修改从源点v0到集合T中剩余结点的当前最短路径长度值，集合T中各结点的新的当前最短路径的长度值，为原来的最短路径

2、的长度值与从源点过结点u到达该结点的路径长度中的最小者。此过程不断地重复，直到集合T中的结点全部加入到集合s中为止。三．设计提示题中规定采用邻接表表示图，假设图中有n个顶点，则考虑邻接表表头结点为head[0]，head[1]，head[2]，…，head[n-1]，链表中每个结点有三个字段：其中，vertex——顶点字段，存放顶点序号；cost——表头顶点到该顶点之边上的权值；link——连接同一链中的下一个顶点。采用数组dist[j](0≤j≤n-1)存放从源点v0到顶点vj的最短路径长度，dist[0]=0，如果源点v0到顶点v

3、x无通路，则dist[x]=max（计算机允许的最大值）。采用n-1个数组分别存放源点v0到其余n-1个顶点之最短路径上的顶点（序号）。采用数组S指示已找到最短路径的顶点。S[j]=0表示顶点j不在数组中，S[j]=1表示顶点j在数组中(0≤j≤n-1)。四.设计思想打印构图求最短路径调用creatgraph输入点边信息输出（可用递归）排序构图比较简单。求最短路径是修改的书上的Dijkstra函数，书上的图是用邻接矩阵存储的，我按照题目要求改为邻接链表，但是思想一样。排序借用了冒泡排序法。输出最短路径是自己设计的一个递归函数。函数体如

4、下：voidDijkstra(AdjLGraphG,intv0,intdistance[],intpath[])/*带权图G从下标v0顶点到其它顶点的最短距离distance*//*和最短路径下标path*/{Edge*p;intn=G.numOfVerts;int*s=(int*)malloc(sizeof(int)*n);intminDis,i,j,u;/*初始化*/for(i=0;i

5、adj;while(p!=NULL){distance[p->dest]=p->cost;path[p->dest]=G.a[v0].data;p=p->next;}s[v0]=1;/*在还未找到最短路径的顶点集中选有最短距离的顶点u*/for(i=1;i

6、;s[u]=1;/*标记顶点u已从集合T加入到集合S中*//*修改从v0到其它顶点的最短距离和最短路径*/p=G.a[u].adj;while(p!=NULL){if(s[p->dest]==0&&distance[u]+p->costdest]){distance[p->dest]=distance[u]+p->cost;path[p->dest]=G.a[u].data;}p=p->next;}}}voidprintpath(inti,intstart,intpath[],inta[]){intj,u;u

7、=0;if(path[i]==start){printf("%d",start);return;}for(j=0;j<6;j++){if(a[j]!=path[i]){u++;}if(a[j]!=path[i])break;}printpath(u,start,path,a);printf("%d",path[i]);}源代码：#include#includetypedefintDataType;#defineMaxSize100#defineMaxVertices10#defineMaxEdge

8、s100#defineMaxWeight10000//********邻接表的存储结构***********typedefstructNode{intcost;intdest;/*邻接边的弧头顶点序号*/structNo