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

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

2、數(shù)組 就會發(fā)生相應的變化。用普里姆算法從頂點U出發(fā)構(gòu)造網(wǎng)G的最小生成樹stmct Closedge( vertextype adjvex; U 集中的頂點int lowcost; / 邊的權值 closedgeMAX.VERTEX.NUM;void MiniSpanTiee_P(mgraph Q vertextype u)( int k = Locate(&G；u );若圖G中存在頂點u,則返回u在圖中的存儲位置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, ”；/輸出生成樹上一條邊closedgefk .lowcost=0; 第 k 頂點并入 U 集for (j=0; jG.vexiium; +j)修改其它頂點的最小邊if (G.arcsk j closedge j . lowcost)( clo sedge j . adj vex= Gvexsk;closedgej.lowcost=G.aicskj;)/if) /for /MiniSpaiiTree_P查找最小未被訪問的邊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存放頂點i的當前最短路徑長度charpathnn+1 ; /pathi+存放頂點i的當前最短路徑。bool flagn; 表示當前最短路徑是否己經(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個頂點的最短路徑 ( 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;拓撲排序：操作方法：(1)選取一個沒有前驅(qū)的頂點，輸出它，并從AOV中網(wǎng)中刪除此頂點以及所有以它 為尾的孤。(2)重復(1)直至輸出所有結(jié)點統(tǒng)計有向圖鄰接表各頂點的入度void uiit_iiidegree(ALGraph G)fbr(i=O:iGvexiium;i+)mdegreei=O;fbr(i=O; iadjvex

7、+; p=p-nextarc;/fbr /imciiidegree取入度為零的點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.算法實現(xiàn)m=0:Hut_mdegree(G);vr=getzerodegree(G)wliile(v!=-l)(