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

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

2、度中的最小者。此过程不断地重复，直到集合T中的结点全部加入到集合s中为止。三设计提示题中规定采用邻接表表示图，假设图中有n个顶点，则考虑邻接表表 头结点为head0，head1，head2，headn-1，链表中每个结点有 三个字段： 其中，vertex顶点字段，存放顶点序号； cost表头顶点到该顶点之边上的权值； link连接同一链中的下一个顶点。 采用数组distj(0jn-1)存放从源点v0到顶点vj的最短路径长度， dist0=0，如果源点v0到顶点vx无通路，则distx=max（计算机允许的最 大值）。 采用n-1个数组分别存放源点v0到其余n-1个顶点之最短路径上的顶点 （序号

3、）。采用数组S指示已找到最短路径的顶点。Sj=0表示顶点j不在 数组中，Sj=1表示顶点j在数组中(0jn-1)。四.设计思想打印构图求最短路径调用creatgraph输入点边信息输出（可用递归）排序构图比较简单。求最短路径是修改的书上的Dijkstra函数，书上的图是用邻接矩阵存储的，我按照题目要求改为邻接链表，但是思想一样。排序借用了冒泡排序法。输出最短路径是自己设计的一个递归函数。函数体如下：void Dijkstra(AdjLGraph G, int v0, int distance, int path)/*带权图G从下标v0顶点到其它顶点的最短距离distance*/*和最短路径下标

4、path*/ Edge *p;int n=G.numOfVerts; int *s = (int *)malloc(sizeof(int)*n); int minDis, i,j,u; /*初始化*/ for(i = 0; i dest=p-cost; pathp-dest=G.av0.data; p=p-next; sv0 = 1; /*在还未找到最短路径的顶点集中选有最短距离的顶点u*/ for(i = 1; i n; i +) minDis = MaxWeight;for(j = 0;j =n;j +) if(sj = 0 & distancej dest = 0 & distanceu

5、 +p-cost dest) distancep-dest = distanceu +p-cost; pathp-dest =G.au.data; p=p-next; void printpath(int i,int start,int path,int a) int j,u; u=0; if(pathi=start) printf(%d,start); return;for(j=0;j6;j+)if(aj!=pathi)u+;if(aj!=pathi)break; printpath(u,start,path,a); printf(%d,pathi); 源代码：#include #inclu

6、de typedef int DataType;#define MaxSize 100#define MaxVertices 10#define MaxEdges 100#define MaxWeight 10000/*邻接表的存储结构*typedef struct Node int cost;int dest;/*邻接边的弧头顶点序号*/struct Node *next;Edge;/*邻接边单链表的结点结构体*/typedef structDataType data;/*顶点数据元素*/int source;/*邻接边的弧尾顶点序号*/Edge *adj;/*邻接边的头指针*/ AdjLH

7、eight; /*数组的数据元素类型结构体*/typedef struct AdjLHeight aMaxVertices;/*邻接表数组*/ int numOfVerts;/*顶点个数*/ int numOfEdges;/*边个数*/ AdjLGraph;/*邻接表结构体*/typedef structint row;int col;int weight;RowCol;void AdjInitiate(AdjLGraph *G)int i;G-numOfVerts=0;G-numOfEdges=0;for(i=0;iai.source=1;G-ai.adj=NULL;void InsertV

8、ertex(AdjLGraph *G,int i,DataType vertex)if(i=0&iai.data=vertex;G-numOfVerts+;else printf(定点越界);void InsertEdge(AdjLGraph *G,int v1,int v2,int cost)Edge *p;if (v1=G-numOfVerts|v2=G-numOfVerts) printf(v1 or v2越界);return ;p=(Edge *)malloc(sizeof(Edge);p-dest=v2;p-cost=cost;p-next=G-av1.adj;G-av1.adj=p

9、;G-numOfEdges+;int GeFirstVex(AdjLGraph *G,int v)Edge *p;if (v=G-numOfVerts) printf(v越界);return -1;p=G-av.adj;if(p!=NULL)return p-dest;else return -1;int GetNextVex(AdjLGraph *G,int v1,const int v2)Edge *p;if (v1=G-numOfVerts|v2=G-numOfVerts) printf(v1 or v2越界);return -1;p=G-av1.adj;while(p!=NULL)if

10、(p-dest!=v2)p=p-next;continue;else break;p=p-next;if(p!=NULL)return p-dest;else return -1;void CreateGraph(AdjLGraph *G,DataType v,int n,RowCol d,int e)int i,k;AdjInitiate(G);for(i=0;in;i+) InsertVertex(G, i,vi);for(k=0;ke;k+)InsertEdge(G,dk.row,dk.col,dk.weight);/*zhunbeigongzuo*/888888888888888888

11、88888888888888888888888888888888888888888888888888888888888void Dijkstra(AdjLGraph G, int v0, int distance, int path)/*带权图G从下标v0顶点到其它顶点的最短距离distance*/*和最短路径下标path*/ Edge *p;int n=G.numOfVerts; int *s = (int *)malloc(sizeof(int)*n); int minDis, i,j,u; /*初始化*/ for(i = 0; i dest=p-cost; pathp-dest=G.av

12、0.data; p=p-next; sv0 = 1; /*在还未找到最短路径的顶点集中选有最短距离的顶点u*/ for(i = 1; i n; i +) minDis = MaxWeight;for(j = 0;j =n;j +) if(sj = 0 & distancej dest = 0 & distanceu +p-cost dest) distancep-dest = distanceu +p-cost; pathp-dest =G.au.data; p=p-next; /888888888888888888888888888888888888888888888888888888888

13、8888888888888888888888888888888888888888/8888888888888888888888888888888888888888888888888888888888888void BubbleSort(DataType a,int distance,int path,int n)int i,j,flag=1;DataType temp;for(i = 1;i n & flag = 1; i+) flag = 0; for(j = 0;j distancej+1) flag = 1; temp = aj; aj = aj+1; aj+1 = temp;temp

14、= pathj; pathj = pathj+1; pathj+1 = temp;temp = distancej; distancej = distancej+1; distancej+1 = temp; void printpath(int i,int start,int path,int a) int j,u; u=0; if(pathi=start) printf(%d,start); return;for(j=0;j6;j+)if(aj!=pathi)u+;if(aj!=pathi)break; printpath(u,start,path,a); printf(%d,pathi);

15、 /88888888888888888888888888888888888888888888888888888888888888888888888main()AdjLGraph g1;int aMaxVertices;RowCol rowMaxEdges;int i,j,k,v0;int distance6,path6;printf(请输入图的点的个数);scanf(%d,&i);printf(请输入图的边的个数);scanf(%d,&j);for(k=0;ki;k+)printf(请输入图的点);scanf(%d,&ak);for(k=0;kj;k+)printf(请输入图的边终点在数组中的下标值);scanf(%d,&rowk.col);printf(请输入图的边起点在数组中的下标值);scanf(%d,&rowk.row);printf(请输入图的边的值n);scanf(%d,&rowk.weight);CreateGraph(&g1,a,i,row,j);printf(请输入起点在数组