最小生成樹和最短路徑-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)(參考版)
2025-06-26 20:11本頁面
【正文】 Dijkstra算法的時(shí)間復(fù)雜度為O(n^2)。(4) 在實(shí)現(xiàn)Dijkstra算法時(shí)附設(shè)了二維數(shù)組P記錄從V0到各頂點(diǎn)的最短路徑上包含的頂點(diǎn)，用數(shù)組D記錄各最短路徑的長度，此外還附設(shè)了一個(gè)隊(duì)列Q，將每次找到的最短路徑的終點(diǎn)入隊(duì)，最后輸出最短路徑時(shí)根據(jù)當(dāng)時(shí)入隊(duì)的順序依次輸出，這里隊(duì)列可以用一維數(shù)組代替，用隊(duì)列可以更好地體現(xiàn)算法的思想。(3) 在實(shí)現(xiàn)Kruskal算法時(shí)為所有頂點(diǎn)附設(shè)一個(gè)數(shù)組Vset，標(biāo)記各頂點(diǎn)所處的連通分量，還附設(shè)了一個(gè)結(jié)構(gòu)體變量存放各邊的起點(diǎn)、終點(diǎn)和邊的權(quán)值；在對各邊按權(quán)值大小進(jìn)行排序時(shí)，采用的是堆排序，初始建的是大頂堆，最終排完序后就是按邊權(quán)值從小到大的有序序列。 } }運(yùn)行結(jié)果： 【小結(jié)或討論】(1) 通過本次實(shí)驗(yàn)，掌握了最小生成樹以及最短路徑的相關(guān)概念，并且會實(shí)現(xiàn)Prim算法、Kruskal算法以及Dijkstra算法。 39。j。 39。i。 printf(%s到各頂點(diǎn)的最短路徑為：\n,[0])。Q,amp。i6。 int t[6]。i。 } printf(%s到各頂點(diǎn)的最短路徑長度為：\n,[0])。++j) printf(%2d,p[i][j])。++i) { for(j=0。 for(i=0。d)。 ShortestPath_DIJ(g,v0,amp。 CreateDN(amp。 PathMatrix p。 int i,j,e,v0=0。 } } } } void main() { InitQueue(amp。++j) (*P)[w][j]=(*P)[v][j]。 for(j=0。amp。amp。amp。w。Q,v)。 } /* w頂點(diǎn)離v0頂點(diǎn)更近 */ final[v]=TRUE。++w) if(!final[w]) /* w頂點(diǎn)在VS中 */ if((*D)[w]min) { v=w。 /* 當(dāng)前所知離v0頂點(diǎn)的最近距離 */ for(w=0。i。 final[v0]=TRUE。 (*P)[v][v]=TRUE。++w) (*P)[v][w]=FALSE。 for(w=0。++v) { final[v]=FALSE。 for(v=0。 */ /* final[v]為TRUE當(dāng)且僅當(dāng)v∈S,即已經(jīng)求得從v0到v的最短路徑 */ int v,w,i,j,min。 }void ShortestPath_DIJ(MGraph G,int v0,PathMatrix *P,ShortPathTable *D) { /* 用Dijkstra算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑P[v]及帶權(quán)長度 */ /* D[v]。 free(p)。 (*Q).frontnext=pnext。 p=(*Q).frontnext。 } Status DeQueue(LinkQueue *Q,QElemType *e) { /* 若隊(duì)列不空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR */ QueuePtr p。 (*Q).rear=p。 pnext=NULL。 if(!p) /* 存儲分配失敗 */ exit(OVERFLOW)。 else return FALSE。 return OK。 if(!(*Q).front) exit(OVERFLOW)。 LinkQueue Q。 typedef struct { QueuePtr front,rear。 struct QNode *next。 } typedef int QElemType。 /* 有向網(wǎng) */ } (*G).kind=DN。 j=LocateVex(*G,vb)。w)。k(*G).arum。 /* 網(wǎng) */ } printf(請輸入%d條弧的弧尾 弧頭 權(quán)值(以空格作為間隔): \n,(*G).arum)。j(*G).vexnum。i(*G).vexnum。++i) /* 構(gòu)造頂點(diǎn)向量 */ scanf(%s,(*G).vexs[i])。 for(i=0。(*G).arum)。 scanf(%d,%d,amp。 VertexType va,vb。 return 1。i。否則返回1 */ int i。typedef int ShortPathTable[MAX_VERTEX_NUM]。 /* 圖的種類標(biāo)志 */}MGraph。 /* 鄰接矩陣 */ int vexnum,arum。typedef struct{ VertexType vexs[MAX_VERTEX_NUM]。對無權(quán)圖，用1(是)或0(否)表示相鄰否； */ /* 對帶權(quán)圖，c則為權(quán)值類型 */ InfoType *info。 /* {有向圖,有向網(wǎng),無向圖,無向網(wǎng)} */typedef struct{ VRType adj。typedef char VertexType[MAX_NAME]。 // 布爾類型
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1