【正文】 if(l0)closeEdge[i].lowcost=l。i++) //雙重循環(huán)復(fù)雜度 O(n2)與邊數(shù)無關(guān) { k=minimum(closeEdge,n)。 cout“\n”v“ ”w“ ”lendl。j++) //更新 closeEdge { v=GetVertex(G,j)。lcloseEdge[j].lowcost) { closeEdge[j].lowcost=l。 ConnectedComponent(G)。 2. 重復(fù) 1 n1次直到 T連通。 C B E A F D 問題： 分支？ ？ 并查集 MFS方法 問題： 分支？ 用 雙親表示法 表示結(jié)點，每個結(jié)點都有一個數(shù)據(jù)和一個指向雙親的地址的指針。兩個結(jié)點各自所在分支的根相同，則他們處在同一分支，根不同，則所在分支不同。 0≠2，根不同，分支不同。 } 樹的雙親表示法定義 template class T class PTree { PNodeT nodes[MAX_TREE_SIZE]。 int PTreeInsert(T item, int pr)。 int FindRoot(int i)。 并查集類的定義 template class T int MFSet T ::Find(T item) { for(int i=0。} return 1。j=nodes[j].parent)； return j。 } nodes[root2].parent=root1。 //Kruskal算法 define MaxInt 32767 include include include include include typedef EdgeInfochar EI。 MFSet T MFS。i++) { item=GetVertex(G,i)。i++) { u=GetVertex(G,i)。 l=(u,v)。 =v。 while(countn) { edge=( )。 (i,j)。 coutendl。 } 圖上兩點間最短距離 A D B C E F 4 6 20 14 6 6 12 8 12 2 4 10 4 五、最短路徑 兩點間邊數(shù)最少的路徑 可用作交通自動咨詢系統(tǒng) 兩點間邊權(quán)重的和最小的路徑 用來計算兩城市間路程最短， 時間最快，費用最省的路徑 兩點 A,B之間邊數(shù)最少的路徑 從 A點出發(fā)，對圖做廣度優(yōu)先遍歷。 D[i]=從源點 v0到頂點 vi最短路經(jīng)的長度。 第二步 v3 v0 v5 v2 v4 50 v1 5 30 60 100 10 10 1 2 3 4 5 6 j D[I] 10 30 100 2 D[i] 60 4 j2=4 D[4]=30 是 v0到 v4的最短路徑的長度 20 L={v0,v2} L={v0,v2,v4} 遞歸過程：重復(fù)第二步 設(shè)已經(jīng)有 v0到 vj1 ,vj2,vjk1}是已經(jīng)求得的從 v0出發(fā)的最短路徑的終點的集合，可以證明下一條最短路徑 (終點 vjk),是只通過 S中頂點到達 vjk的 。v p }。 } //用優(yōu)先序列實現(xiàn)最短路徑算法 template class T int Graph T ::MinimumPath(const T amp。 SeqList T L, adjL。 = sVertex。 while (!( )) { pathData = ( )。 if (!FindVertex(L,ev)) {(ev)。 for(( )。 = ev。 else return 1。 } VertexIteratorT liter(G)。 i != pos) { i++。 T u,v,w。in。jn。P[i][i]=1。in。j++) //Get the minimum D[k] if(final[j]==0) //vertex j has not marked. if(D[j]min) { k=j。 //found the shortest path for(j=1。 if(!final[j]amp。 P[j][j]=1。 int *D=new int[n]。in。jn。如果經(jīng)過頂點 k,則最短 kpath是 從 u到 k的最短 (k1)path,再連接從 k到 v的最短 (k1)path。 D1[i][j]=arc[i][j]。P, DistanceMatrixamp。 for(i=0。jn。 if(l0)D[i][j]=l。 if(D[i][j]MaxInt) {P[i][j][i]=1。k++) for(i=0。j++) if(D[i][k]+D[k][j]D[i][j]) { D[i][j]=D[i][k]+D[k][j]。 }。tn。i++) for(j=0。} } for(k=0。kn。 D[i][j]=MaxInt。i++) { u=GetVertex(G,i)。 int i,j,k,l,t。 typedef int** PathMatrix。 v0 v2 3 v1 2 4 6 11 D D1 D0 D1 D2 0 1 2 0 1 2 0 1 2 0 1 2 0 0 4 11 0 4 11 0 4 6 0 4 6 1 6 0 2 6 0 2 6 0 2 5 0 2 2 3 ∞ 0 3 7 0 3 7 0 3 7 0 P P1 P0 P1 P2 0 1 2 0 1 2 0 1 2 0 1 2 0 v0v1 v0v2 v0v1 v0v2 v0v1 v0v1v2 v0v1 v0v1v2 1 v1v0 v1v2 v1v0 v1v2 v1v0 v1v2 v1v2v0 v1v2 2 v2v0 v2v0 v2v0v1 v2v0 v2v0v1 v2v0 v2v0v1 弗洛伊德 Floyd算法 int **D=new (int**[n])[n]。 cout}endl。 coutP[i][0]。 ShortestPathDijkstra(G,0,D,P)。 ()。(lD[w])) { D[w]=l。j++) { w=GetVertex(G,j)。} final[k]=1。 for(j=1。 final[v0]=1。//initial P[i][j] D[i]=(u,v)。 v=GetVertex(G,i)。 int *final=new int[n]。 } return ( )。 while(!( ) amp。 if(pos0||pos=n) {cerrThere are not so many vertices!。 (pathData)。 ( )) { ev = ( )。 adjL = GetNeighbors(sv)。 mincost = 。 = 0。 T sv, ev。 eVertex) { PQueue PathInfo T PQ(MaxGraphSize)。 a, const PathInfo T amp。 template class T struct PathInfo { T startV, endV。vp長 應(yīng)當先有 v0,vjk, 更新 D[i]=min{D[i], D[jk]+arc[jk][i]} 令 D[jk+1]=min{D[i], in,i≠ j1 ,j2 第一步 v3 v0 v5 v2 v4 50 v1 5 30 60 100 10 10 1 2 3 4 5 6 D[i] 10 30 100 j1=2 D[2]=10 是 v0到 v2的最短路徑的長度 20 L={v0} L={v0,v2} 迪克斯特拉 Dijkstra算法 已經(jīng)有 L={v0,v2} ，下一條最短路徑 (終點 vj2),或者是 (v0 vj2), 或者是 (v0, vj1,vj2) 。 單源點到其余各點權(quán)重和最小的路徑 從 v0到其余各點的最短路徑 v3 v0 v5 v2 v4 50 v1 5 30 60 100 20 10 10 起點 終點 最短路徑 長度 v0 v1 v2 v3 v4 v5 (v0,v4) 30 (v0,v2) 10 (v0,v4,v3) 50 (v0,v4,v3,v5) 60 迪克斯特拉 Dijkstra算法 按路徑長度遞增逐步產(chǎn)生最短路徑 設(shè)集合 S存放已經(jīng)求出的最短路徑的終點，開始，S中只有一個源點 v0，以后每求得的一條最短路徑就將終點加入 S，直到全部頂點都加入到 S. 定義一個數(shù)組 D[n]。 coutendl。 } } } void main( ) { Graphchar G。 j=()。 (edge)。amp。jn。 } for(i=0。 for(i=0。 T item,u,v。 int cost。 return FindRoot(i)。 for(int j=i。i++) if(nodes[i].data==item) { return i。 void Merge(int root1,int root2)。 int PTreeSize( )。 //number of nodes public: PTree( int m=0)。 雙親表示法結(jié)點定義 define MAX_TREE_SIZE 100 template class T struct PNode { T data。 C B E A F D G H C B E A F D G H 雙親表示法 用 數(shù)組 存儲樹的結(jié)點 每個結(jié)點中附設(shè)一個字段 指示其父結(jié)點的位置 A B C D E F G H 0 1 2 3 4 5 6 7 A 1 B 1 C 1 D 1 E 1 F 1 G 1 H 1 A B C D E F G H 0 1 2 3 4 5 6 7 A 1 B 1 C 1 D 1 E