數(shù)據(jù)結(jié)構(gòu) Prim及單源最短路徑

1、用普里姆算法從頂點(diǎn)U出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)為實(shí)現(xiàn)此算法需附設(shè)一個(gè)輔助數(shù)組closedge,用以記錄從U到V-U具有最小代價(jià)的邊。 對(duì)每個(gè)頂點(diǎn)viEV-U ,在輔助數(shù)組中存在一個(gè)相應(yīng)分量closedgei-l,它包括兩個(gè)域:lowcost 和 adj vex olowcost域：存儲(chǔ)最小代價(jià)的邊上的權(quán)值，即：closedgei-l.lowcost=nihi(cost(u, vi )|uEUcost(u,vi)表示邊(u,vi)上的權(quán)值。若某頂點(diǎn)加入到U中，則此時(shí)置lowcost域?yàn)?,表示該 頂點(diǎn)并入U(xiǎn)中。adjvex域：存儲(chǔ)依附于該邊在U中的頂點(diǎn)。顯然，每加入一個(gè)頂點(diǎn)到U中,closedge

2、數(shù)組 就會(huì)發(fā)生相應(yīng)的變化。用普里姆算法從頂點(diǎn)U出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)stmct Closedge( vertextype adjvex; U 集中的頂點(diǎn)int lowcost; / 邊的權(quán)值 closedgeMAX.VERTEX.NUM;void MiniSpanTiee_P(mgraph Q vertextype u)( int k = Locate(&G；u );若圖G中存在頂點(diǎn)u,則返回u在圖中的存儲(chǔ)位置for (iiitj=O; jG.vexiium; +j)輔助數(shù)組初始化】f(j!=k) closedgej.adjvex=u;closedge!j.lowcost=GarcskIj;

3、closedgek.lowcost = 0;/ 初始，U=ufor (mt i=l; iHG.vexskH, ”；/輸出生成樹(shù)上一條邊closedgefk .lowcost=0; 第 k 頂點(diǎn)并入 U 集for (j=0; jG.vexiium; +j)修改其它頂點(diǎn)的最小邊if (G.arcsk j closedge j . lowcost)( clo sedge j . adj vex= Gvexsk;closedgej.lowcost=G.aicskj;)/if) /for /MiniSpaiiTree_P查找最小未被訪問(wèn)的邊mt niuumum(mgraph G, Closedge cl

4、osedge n) ( int k;fbr(int i=0; iG. vexiium;i-H-)if(closedgei.lowcost!=0) k=i; break; fbr( ;iG.vexnum:i+)if(closedgei. lowcost! =0&closedgei.lowcostclosedgek.lowcost) k=i；return k;uit distn; /disti存放頂點(diǎn)i的當(dāng)前最短路徑長(zhǎng)度charpathnn+1 ; /pathi+存放頂點(diǎn)i的當(dāng)前最短路徑。bool flagn; 表示當(dāng)前最短路徑是否己經(jīng)被選擇void ShortestPath.DJS(mgraph

5、 g, mt vO)( mtchar tail2;fbr (i =0; ig.vexiium; i+) ( flagi=false;disti=g.aicsOi;pathi0=v0+H;pathil=g.vexsi;pathW;fbr(mt t=l; tg.vexiium; t+)/求vO到其余n-1個(gè)頂點(diǎn)的最短路徑 ( niiii=MAX;fbr (1=0; ig.vexiium; i+)if (disti inm&flagi=false) k = i: nuii=disti; flagk=tine;fbr (i =0; ig.vexiium; i+)if (distk+g.arcskidi

6、sti) disti=distk+ g.arcski; strcpy(pathi,pathk);tailO=i+a;taill=，()； sticat(pathijail); )for (i =0; ig.vexiium; i+) coutpathiH Mdistiendl;拓?fù)渑判颍翰僮鞣椒ǎ?1)選取一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)，輸出它，并從AOV中網(wǎng)中刪除此頂點(diǎn)以及所有以它 為尾的孤。(2)重復(fù)(1)直至輸出所有結(jié)點(diǎn)統(tǒng)計(jì)有向圖鄰接表各頂點(diǎn)的入度void uiit_iiidegree(ALGraph G)fbr(i=O:iGvexiium;i+)mdegreei=O;fbr(i=O; iadjvex

7、+; p=p-nextarc;/fbr /imciiidegree取入度為零的點(diǎn)vmt getzerodegree (ALGrapg G) ( fbr(i=O;iadj vex;elsereturn-!;5 . NextAdjmt NextAdj (ALGrapg G .int v int w)(p=G vertices v .firs taic;while(p & p-adjvex! =w)p=p-nextaic;f(p)return p-nextarc-adjvex;elsereturn-!;6.算法實(shí)現(xiàn)m=0:Hut_mdegree(G);vr=getzerodegree(G)wliile(v!=-l)(