【正文】 )) { if (!(( ))) { ( )。 SeqListIteratorT liter(L)。!( )。 (( ))。 cout endl。 Prim 普里姆算法 設(shè) G=V,E, 1. 令 U={v0}, T={ }. 2. 對任意 u∈ U, v∈ VU, (u,v)∈ E, 找到權(quán)最小的邊 (u1,v1), 令 U=U∪ {v1}, T=T∪ {(u1,v1)} 3. 重復(fù) 2，直至 U=V. 得到 T就是最小生成樹。 int lowcost。 template class T int operator(MiniCostEdgeInfoT a, MiniCostEdgeInfoT b) { return 。in。 int min=i。in。amp。 return min。 if(pos0||pos=n) {cerrThere are not so many vertices!。 } VertexIteratorT liter(G)。 while(!( ) amp。 i != pos) { i++。 } return ( )。 MiniCostEdgeInfo T * closeEdge。 T s,w, v=GetVertex(G,0)。//起始點(diǎn) v0加進(jìn) U for(int i=1。i++)//初始化 closeEdge數(shù)組 { w=GetVertex(G,i)。 closeEdge[i].adjvex=v。 else closeEdge[i].lowcost=maxint。in。 //確定 closeEdge中最小值 v=closeEdge[k].adjvex。 l=closeEdge[k].lowcost。 closeEdge[k].lowcost=0。jn。 l=(w,v)。amp。 closeEdge[j].adjvex=w。 ()。 MiniSpanTreePrim(G)。 1. 選擇 E中權(quán)值最小的邊， 若該邊連接 T的兩個(gè)連通分量，將它加入 T, 這時(shí) T的連通分量減少 1； 否則選下一條權(quán)值最小的邊。 T 就是最小生成樹 C B E A F D 6 5 3 6 4 5 2 1 5 6 C B E A F D 6 5 3 6 4 5 2 1 5 6 C B E A F D T={ (A,C), (D,F), (B,E) } T={ (A,C), (D,F), (B,E), (C,F) } T={ (A,C), (D,F), (B,E) (C,F), (B,C) } Kruskal 克魯斯卡爾算法 把所有邊都放進(jìn)優(yōu)先隊(duì)列。否則放棄。根結(jié)點(diǎn)的雙親為 1。從每個(gè)結(jié)點(diǎn)都可以向上找到這個(gè)分支的根。 C B E A F D G H 問題 ？ 將第二個(gè)分支與第三個(gè)分支連起來，只要讓結(jié)點(diǎn)D的雙親由 1改為指向 A。 同樣查到 G所在分支的根是 2， C點(diǎn)。 將 C連到 A,即 C點(diǎn)的雙親改為 0，就可以。 int Parent。 int n。 PNodeT operator[ ](int i)。 T PTreeDelete(int i)。 } include templateclass T class MFSet:public PTree T { public: MFSet( ){ } int Find(T item)。 int FindRoot(T item)。 }。in。 break。 } template class T int MFSet T ::FindRoot(int i) { if(i0||i=n)return 1。nodes[j].parent=0。 } template class T int MFSet T ::FindRoot(T item) { int i=Find(item)。 } template class T void MFSet T ::Merge(int root1, int root2) { if(root10||root1=n||root21||root2=n) { cerrBeyound the scope!。 } include include define maxint 32767 template class T struct EdgeInfo { T beginVex, endVex。 }。 template class T void MiniSpanTreeKruskal(Graph T G) { int i, j, l, n=( )。 EI edge。 PQueueEI L。in。 (item,1)。in。 for(j=0。j++) { v=GetVertex(G,j)。 if(l!=MaxIntamp。l0) { =u。 =l。 } } } int count=1。 i=()。 if(i!=j) { cout endl。 count++。 ()。 coutendl。 MiniSpanTreeKruskal(G)。 從根 A到 B的路徑就是邊數(shù)最少的路徑，也就是中轉(zhuǎn)次數(shù)最少的路徑。 n是圖的頂點(diǎn)數(shù)。 第一步 取 D[i]為 v0到 vi的邊的權(quán)值 ，無邊時(shí)取值 ∞， 取一個(gè)最小值 D[j1]=min{D[i], in} D[j1]是 v0到 vj1的最短路徑的長度。 對每個(gè)頂點(diǎn) vi, 比較 D[i]與 D[j1]+arc[j1][i], 取其小 更新 D[i]=min{D[i], D[j1]+arc[j1][i]} 取 D[j2]=min{D[i], in,i≠j1 } 則 D[j2]是 v0到 vj2的最短路徑的長度。,vjk的最短路徑 對每個(gè)頂點(diǎn) vi, vi ≠ vj1 ,vj2,jk } 則 D[jk+1]是 v0到 vjk+1的最短路徑的長 . v3 v0 v5 v2 v4 50 v1 5 30 60 100 10 10 1 2 3 4 5 L D[i] 0 10 (v0,v2) 30 (v0,v4) 100 (v0,v5) 2 D[i] 0 60 (v0,v2,v3) 4 D[i] 50 (v0,v4,v3) 0 90 (v0,v4,v5) 3 D[i] 0 60 (v0,v4,v3,v5) 5 20 迪克斯特拉 Dijkstra算法 L={v0,v2,v4,v3,v5} 時(shí)間復(fù)雜性 O(n2) 令 L={vj1 ,vj2 否則設(shè) v0到 vjk的路徑中有一個(gè)不在 S中出現(xiàn)的頂點(diǎn) vp，但是路徑 v0v jk比 v0v p的最短路徑，以歸納假設(shè) vp應(yīng)當(dāng)已經(jīng)出現(xiàn)于 L中。 int cost。 template class T int operator = (const PathInfo T amp。 b) { return = 。 sVertex, const T amp。 PathInfo T pathData。 SeqListIterator T adjLiter(adjL)。 int mincost。 = sVertex。 (pathData)。 ev = 。 if (ev == eVertex) break。 sv = ev。 (adjL)。!( )。 if (!FindVertex(L,ev)) { = sv。 = mincost+GetWeight(sv,ev)。 } } } } if (ev == eVertex) return mincost。 } templateclass T T GetVertex(GraphT G,int pos) { int i, n=( )。 return 0。 i = 0。amp。 ( )。 } templateclass T void ShortestPathDijkstra(GraphT G, int v0,int *D,int**P) { int i, j,k,l,min, n=( )。 u=GetVertex(G,v0)。 for( i=0。i++) { final[i]=0。 for(j=0。j++)P[i][j]=0。 //initial D[i] if(D[i]MaxInt){ P[i][v0]=1。} // p[i][j]=1 iff vertex j is in the path from v0 to i } D[v0]=0。 for(i=1。i++) { min=MaxInt。jn。 min=D[j]。 //marked vertex k, v=GetVertex(G,k)。jn。 l=(v,w)+min。amp。 //renew D[w] P[j]=P[k]。 } } } } void main( ) { Graphchar G。 int n=( )。 int **P=new (int**[n])[n]。 for(int i=0。i++) { coutP[i]={ 。 for(int j=1。j++) cout,P[i][j]。 } } 每一對頂點(diǎn)之間的最短路徑 可讓每個(gè)頂點(diǎn)作起始點(diǎn)以用 Dijkstra算法算一遍，共 n遍，時(shí)間復(fù)雜性 O(n3). 弗洛伊德 Floyd算法更直接 弗洛伊德 Floyd算法 定義 Dk(u,v)為從 u到 v的長度最短的 kpath. 假設(shè)已知 從 u到 v的最短 (k1)path，則最短 kpath要么經(jīng)過，要么不經(jīng)過頂點(diǎn) k。如果不經(jīng)過頂點(diǎn) k，則最短路徑保持 k1path不變。 int ***P= new ((int***[n])[n])[n]。 Dk[i][j]=min{Dk1[i][j], Dk1[i][k]+ Dk1[k][j]} include define MaxInt 32767 typedef int** DistanceMatrix。 template class T void ShortestPathFloyd( GraphT G,PathMatrix *amp。 D) { int n=( )。 T u,v,w。in。 for(j=0。j++) { v=GetVertex(G,j)。 l=(u,v)。 for(k=0。k++) P[i][j][k]=0。P[i][j][j]=1。kn。in。jn。 for(t=0。t++) P[i][j][t]=P[i][k][t]||P[k][j][t