數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)三 圖及其應(yīng)用

1、數(shù) 據(jù) 結(jié) 構(gòu) 學(xué)院： 姓名： 班級： 學(xué)號：實(shí)習(xí)三 圖及其應(yīng)用題目：試設(shè)計一個算法，求圖中一個源點(diǎn)到其他各頂點(diǎn)的最短路徑。一.需求分析：設(shè)計要求：（1）用鄰接表表示圖； （2）按長度非遞減次序打印輸出最短路徑的長度及相應(yīng)路徑。二.設(shè)計思想：本程序使用鏈表的形式存儲的。根據(jù)書上的德克斯德拉算法的思想，初始狀態(tài)時，集合s中只包含源點(diǎn)，設(shè)為v0，然后不斷地從集合T中選擇到源點(diǎn)v0路徑長度最短的結(jié)點(diǎn)u加入到集合s中，集合s中每加入一個新的結(jié)點(diǎn)u都要修改從源點(diǎn)v0到集合T中剩余結(jié)點(diǎn)的當(dāng)前最短路徑長度值，集合T中各結(jié)點(diǎn)的新的當(dāng)前最短路徑的長度值，為原來的最短路徑的長度值與從源點(diǎn)過結(jié)點(diǎn)u到達(dá)該結(jié)點(diǎn)的路徑長

2、度中的最小者。此過程不斷地重復(fù)，直到集合T中的結(jié)點(diǎn)全部加入到集合s中為止。三設(shè)計提示題中規(guī)定采用鄰接表表示圖，假設(shè)圖中有n個頂點(diǎn)，則考慮鄰接表表 頭結(jié)點(diǎn)為head0，head1，head2，headn-1，鏈表中每個結(jié)點(diǎn)有 三個字段： 其中，vertex頂點(diǎn)字段，存放頂點(diǎn)序號； cost表頭頂點(diǎn)到該頂點(diǎn)之邊上的權(quán)值； link連接同一鏈中的下一個頂點(diǎn)。 采用數(shù)組distj(0jn-1)存放從源點(diǎn)v0到頂點(diǎn)vj的最短路徑長度， dist0=0，如果源點(diǎn)v0到頂點(diǎn)vx無通路，則distx=max（計算機(jī)允許的最 大值）。 采用n-1個數(shù)組分別存放源點(diǎn)v0到其余n-1個頂點(diǎn)之最短路徑上的頂點(diǎn) （序號

3、）。采用數(shù)組S指示已找到最短路徑的頂點(diǎn)。Sj=0表示頂點(diǎn)j不在 數(shù)組中，Sj=1表示頂點(diǎn)j在數(shù)組中(0jn-1)。四.設(shè)計思想打印構(gòu)圖求最短路徑調(diào)用creatgraph輸入點(diǎn)邊信息輸出（可用遞歸）排序構(gòu)圖比較簡單。求最短路徑是修改的書上的Dijkstra函數(shù)，書上的圖是用鄰接矩陣存儲的，我按照題目要求改為鄰接鏈表，但是思想一樣。排序借用了冒泡排序法。輸出最短路徑是自己設(shè)計的一個遞歸函數(shù)。函數(shù)體如下：void Dijkstra(AdjLGraph G, int v0, int distance, int path)/*帶權(quán)圖G從下標(biāo)v0頂點(diǎn)到其它頂點(diǎn)的最短距離distance*/*和最短路徑下標(biāo)

4、path*/ Edge *p;int n=G.numOfVerts; int *s = (int *)malloc(sizeof(int)*n); int minDis, i,j,u; /*初始化*/ for(i = 0; i < n; i +) distancei =MaxWeight; si = 0; pathi = -1; distancev0=0; p=G.av0.adj; while(p!=NULL) distancep->dest=p->cost; pathp->dest=G.av0.data; p=p->next; sv0 = 1; /*在還未找到最

5、短路徑的頂點(diǎn)集中選有最短距離的頂點(diǎn)u*/ for(i = 1; i < n; i +) minDis = MaxWeight;for(j = 0;j <=n;j +) if(sj = 0 && distancej < minDis) u = j; minDis = distancej; /*當(dāng)已不再存在路徑時算法結(jié)束*/if(minDis = MaxWeight) return;su = 1; /*標(biāo)記頂點(diǎn)u已從集合T加入到集合S中*/*修改從v0到其它頂點(diǎn)的最短距離和最短路徑*/p=G.au.adj;while(p!=NULL) if(sp->dest

6、 = 0 && distanceu +p->cost < distancep->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;j<6;j+)if(aj!=pathi)u+;if(a

7、j!=pathi)break; printpath(u,start,path,a); printf("%d",pathi); 源代碼：#include <stdio.h>#include <malloc.h>typedef int DataType;#define MaxSize 100#define MaxVertices 10#define MaxEdges 100#define MaxWeight 10000/*鄰接表的存儲結(jié)構(gòu)*typedef struct Node int cost;int dest;/*鄰接邊的弧頭頂點(diǎn)序號*/struct

8、 Node *next;Edge;/*鄰接邊單鏈表的結(jié)點(diǎn)結(jié)構(gòu)體*/typedef structDataType data;/*頂點(diǎn)數(shù)據(jù)元素*/int source;/*鄰接邊的弧尾頂點(diǎn)序號*/Edge *adj;/*鄰接邊的頭指針*/ AdjLHeight; /*數(shù)組的數(shù)據(jù)元素類型結(jié)構(gòu)體*/typedef struct AdjLHeight aMaxVertices;/*鄰接表數(shù)組*/ int numOfVerts;/*頂點(diǎn)個數(shù)*/ int numOfEdges;/*邊個數(shù)*/ AdjLGraph;/*鄰接表結(jié)構(gòu)體*/typedef structint row;int col;int weig

9、ht;RowCol;void AdjInitiate(AdjLGraph *G)int i;G->numOfVerts=0;G->numOfEdges=0;for(i=0;i<MaxVertices;i+)G->ai.source=1;G->ai.adj=NULL;void InsertVertex(AdjLGraph *G,int i,DataType vertex)if(i>=0&&i<MaxVertices)G->ai.data=vertex;G->numOfVerts+;else printf("定點(diǎn)越界&

10、quot;);void InsertEdge(AdjLGraph *G,int v1,int v2,int cost)Edge *p;if (v1<0|v1>=G->numOfVerts|v2<0|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;G->numOfEdges+;int Ge

11、FirstVex(AdjLGraph *G,int v)Edge *p;if (v<0|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<0|v1>=G->numOfVerts|v2<0|v2>=G->numOfVerts) printf(&quo

12、t;v1 or v2越界");return -1;p=G->av1.adj;while(p!=NULL)if(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;i<n;i+) InsertVertex(G, i,vi);for(k=

13、0;k<e;k+)InsertEdge(G,dk.row,dk.col,dk.weight);/*zhunbeigongzuo*/88888888888888888888888888888888888888888888888888888888888888888888888888888void Dijkstra(AdjLGraph G, int v0, int distance, int path)/*帶權(quán)圖G從下標(biāo)v0頂點(diǎn)到其它頂點(diǎn)的最短距離distance*/*和最短路徑下標(biāo)path*/ Edge *p;int n=G.numOfVerts; int *s = (int *)mallo

14、c(sizeof(int)*n); int minDis, i,j,u; /*初始化*/ for(i = 0; i < n; i +) distancei =MaxWeight; si = 0; pathi = -1; distancev0=0; p=G.av0.adj; while(p!=NULL) distancep->dest=p->cost; pathp->dest=G.av0.data; p=p->next; sv0 = 1; /*在還未找到最短路徑的頂點(diǎn)集中選有最短距離的頂點(diǎn)u*/ for(i = 1; i < n; i +) minDis =

15、MaxWeight;for(j = 0;j <=n;j +) if(sj = 0 && distancej < minDis) u = j; minDis = distancej; /*當(dāng)已不再存在路徑時算法結(jié)束*/if(minDis = MaxWeight) return;su = 1; /*標(biāo)記頂點(diǎn)u已從集合T加入到集合S中*/*修改從v0到其它頂點(diǎn)的最短距離和最短路徑*/p=G.au.adj;while(p!=NULL) if(sp->dest = 0 && distanceu +p->cost < distancep->

16、;dest) distancep->dest = distanceu +p->cost; pathp->dest =G.au.data; p=p->next; /8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888/8888888888888888888888888888888888888888888888888888888888888void BubbleSort(DataType a,int distance,int path

17、,int n)int i,j,flag=1;DataType temp;for(i = 1;i < n && flag = 1; i+) flag = 0; for(j = 0;j < n - i; j+) if(distancej>distancej+1) flag = 1; temp = aj; aj = aj+1; aj+1 = temp;temp = pathj; pathj = pathj+1; pathj+1 = temp;temp = distancej; distancej = distancej+1; distancej+1 = temp;

18、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;j<6;j+)if(aj!=pathi)u+;if(aj!=pathi)break; printpath(u,start,path,a); printf("%d",pathi); /88888888888888888888888888888888888888888888888888888888888888888888888main()AdjLGraph g1;int aMaxVertices;RowCol rowMaxEdges;int i,j,k,v0;int distance6,path6;printf("請輸入圖的點(diǎn)的個數(shù)");scanf("%d",&i);printf("請輸入圖的邊的個數(shù)");scanf("%d",&j);for(k=0;k<i;k+)printf("請輸入圖的點(diǎn)");scanf("%d"