【導讀】無向圖的連通分量和生成樹。圖應用最廣泛的數(shù)據(jù)結構。點之間的關系是任意的。TDODID為整個圖的總度,出度,入度數(shù)。路徑vi······vj,以vi為起點vj為終點的頂點序列。回路環(huán)首尾相接的路徑，有向圖vivj強連通vivj連通vjvi也連通，強連通圖任意兩點都強連通。完全圖任意兩點間都有邊相關聯(lián)的圖。有向完全圖共有邊n(n-1)條。有權圖圖的所有邊都是帶權邊。連通分量一個圖的極大連通子圖。生成樹組成生成森林，共有n-k條邊。若干互不相交的有向樹，叫做生成森林。

　　

【正文】 vj1,vj2) 。 對每個頂點 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的最短路徑的長度。 第二步 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} 遞歸過程：重復第二步 設已經(jīng)有 v0到 vj1 ,vj2,vjk的最短路徑 對每個頂點 vi, vi ≠ vj1 ,vj2,vjk, 更新 D[i]=min{D[i], D[jk]+arc[jk][i]} 令 D[jk+1]=min{D[i], in,i≠ j1 ,j2,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} 時間復雜性 O(n2) 令 L={vj1 ,vj2,vjk1}是已經(jīng)求得的從 v0出發(fā)的最短路徑的終點的集合，可以證明下一條最短路徑 (終點 vjk),是只通過 S中頂點到達 vjk的 。 否則設 v0到 vjk的路徑中有一個不在 S中出現(xiàn)的頂點 vp，但是路徑 v0v pv jk比 v0vp長 應當先有 v0v p的最短路徑，以歸納假設 vp應當已經(jīng)出現(xiàn)于 L中。 template class T struct PathInfo { T startV, endV。 int cost。 }。 template class T int operator = (const PathInfo T amp。 a, const PathInfo T amp。 b) { return = 。 } //用優(yōu)先序列實現(xiàn)最短路徑算法 template class T int Graph T ::MinimumPath(const T amp。 sVertex, const T amp。 eVertex) { PQueue PathInfo T PQ(MaxGraphSize)。 PathInfo T pathData。 SeqList T L, adjL。 SeqListIterator T adjLiter(adjL)。 T sv, ev。 int mincost。 = sVertex。 = sVertex。 = 0。 (pathData)。 while (!( )) { pathData = ( )。 ev = 。 mincost = 。 if (ev == eVertex) break。 if (!FindVertex(L,ev)) {(ev)。 sv = ev。 adjL = GetNeighbors(sv)。 (adjL)。 for(( )。!( )。 ( )) { ev = ( )。 if (!FindVertex(L,ev)) { = sv。 = ev。 = mincost+GetWeight(sv,ev)。 (pathData)。 } } } } if (ev == eVertex) return mincost。 else return 1。 } templateclass T T GetVertex(GraphT G,int pos) { int i, n=( )。 if(pos0||pos=n) {cerrThere are not so many vertices!。 return 0。 } VertexIteratorT liter(G)。 i = 0。 while(!( ) amp。amp。 i != pos) { i++。 ( )。 } return ( )。 } templateclass T void ShortestPathDijkstra(GraphT G, int v0,int *D,int**P) { int i, j,k,l,min, n=( )。 T u,v,w。 u=GetVertex(G,v0)。 int *final=new int[n]。 for( i=0。in。i++) { final[i]=0。 v=GetVertex(G,i)。 for(j=0。jn。j++)P[i][j]=0。//initial P[i][j] D[i]=(u,v)。 //initial D[i] if(D[i]MaxInt){ P[i][v0]=1。P[i][i]=1。} // p[i][j]=1 iff vertex j is in the path from v0 to i } D[v0]=0。 final[v0]=1。 for(i=1。in。i++) { min=MaxInt。 for(j=1。jn。j++) //Get the minimum D[k] if(final[j]==0) //vertex j has not marked. if(D[j]min) { k=j。 min=D[j]。} final[k]=1。 //marked vertex k, v=GetVertex(G,k)。 //found the shortest path for(j=1。jn。j++) { w=GetVertex(G,j)。 l=(v,w)+min。 if(!final[j]amp。amp。(lD[w])) { D[w]=l。 //renew D[w] P[j]=P[k]。 P[j][j]=1。 } } } } void main( ) { Graphchar G。 ()。 int n=( )。 int *D=new int[n]。 int **P=new (int**[n])[n]。 ShortestPathDijkstra(G,0,D,P)。 for(int i=0。in。i++) { coutP[i]={ 。 coutP[i][0]。 for(int j=1。jn。j++) cout,P[i][j]。 cout}endl。 } } 每一對頂點之間的最短路徑 可讓每個頂點作起始點以用 Dijkstra算法算一遍，共 n遍，時間復雜性 O(n3). 弗洛伊德 Floyd算法更直接 弗洛伊德 Floyd算法 定義 Dk(u,v)為從 u到 v的長度最短的 kpath. 假設已知 從 u到 v的最短 (k1)path，則最短 kpath要么經(jīng)過，要么不經(jīng)過頂點 k。如果經(jīng)過頂點 k,則最短 kpath是 從 u到 k的最短 (k1)path,再連接從 k到 v的最短 (k1)path。如果不經(jīng)過頂點 k，則最短路徑保持 k1path不變。 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]。 int ***P= new ((int***[n])[n])[n]。 D1[i][j]=arc[i][j]。 Dk[i][j]=min{Dk1[i][j], Dk1[i][k]+ Dk1[k][j]} include define MaxInt 32767 typedef int** DistanceMatrix。 typedef int** PathMatrix。 template class T void ShortestPathFloyd( GraphT G,PathMatrix *amp。P, DistanceMatrixamp。 D) { int n=( )。 int i,j,k,l,t。 T u,v,w。 for(i=0。in。i++) { u=GetVertex(G,i)。 for(j=0。jn。j++) { v=GetVertex(G,j)。 D[i][j]=MaxInt。 l=(u,v)。 if(l0)D[i][j]=l。 for(k=0。kn。k++) P[i][j][k]=0。 if(D[i][j]MaxInt) {P[i][j][i]=1。P[i][j][j]=1。} } for(k=0。kn。k++) for(i=0。in。i++) for(j=0。jn。j++) if(D[i][k]+D[k][j]D[i][j]) { D[i][j]=D[i][k]+D[k][j]。 for(t=0。tn。t++) P[i][j][t]=P[i][k][t]||P[k][j][t]。