【正文】 B 1 C 1 D 1 E 0 F 1 G 2 H 1 要將 AE， CG相連 只要將 E的雙親改為 0， G的雙親改為 2 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 0 F 1 G 2 H 1 0 1 2 3 4 5 6 7 A 1 B 1 C 0 D 1 E 0 F 1 G 2 H 1 現(xiàn)在要加入邊 EG使連通度減小： 先查 E所在分支的根， E的雙親是 0，即 A點(diǎn)， A的雙親是 1， A是根。 //number of nodes public: PTree( int m=0)。 void Merge(int root1,int root2)。 for(int j=i。 int cost。 for(i=0。jn。 (edge)。 } } } void main( ) { Graphchar G。 單源點(diǎn)到其余各點(diǎn)權(quán)重和最小的路徑 從 v0到其余各點(diǎn)的最短路徑 v3 v0 v5 v2 v4 50 v1 5 30 60 100 20 10 10 起點(diǎn) 終點(diǎn) 最短路徑 長(zhǎng)度 v0 v1 v2 v3 v4 v5 (v0,v4) 30 (v0,v2) 10 (v0,v4,v3) 50 (v0,v4,v3,v5) 60 迪克斯特拉 Dijkstra算法 按路徑長(zhǎng)度遞增逐步產(chǎn)生最短路徑 設(shè)集合 S存放已經(jīng)求出的最短路徑的終點(diǎn)，開(kāi)始，S中只有一個(gè)源點(diǎn) v0，以后每求得的一條最短路徑就將終點(diǎn)加入 S，直到全部頂點(diǎn)都加入到 S. 定義一個(gè)數(shù)組 D[n]。 template class T struct PathInfo { T startV, endV。 eVertex) { PQueue PathInfo T PQ(MaxGraphSize)。 = 0。 adjL = GetNeighbors(sv)。 (pathData)。 while(!( ) amp。 int *final=new int[n]。//initial P[i][j] D[i]=(u,v)。 for(j=1。j++) { w=GetVertex(G,j)。 ()。 coutP[i][0]。 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 i,j,k,l,t。 D[i][j]=MaxInt。} } for(k=0。tn。j++) if(D[i][k]+D[k][j]D[i][j]) { D[i][j]=D[i][k]+D[k][j]。 if(D[i][j]MaxInt) {P[i][j][i]=1。jn。P, DistanceMatrixamp。如果經(jīng)過(guò)頂點(diǎn) k,則最短 kpath是 從 u到 k的最短 (k1)path,再連接從 k到 v的最短 (k1)path。in。 P[j][j]=1。 //found the shortest path for(j=1。in。jn。 T u,v,w。 } VertexIteratorT liter(G)。 = ev。 if (!FindVertex(L,ev)) {(ev)。 = sVertex。 } //用優(yōu)先序列實(shí)現(xiàn)最短路徑算法 template class T int Graph T ::MinimumPath(const T amp。v p 第二步 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的最短路徑的長(zhǎng)度 20 L={v0,v2} L={v0,v2,v4} 遞歸過(guò)程：重復(fù)第二步 設(shè)已經(jīng)有 v0到 vj1 ,vj2 } 圖上兩點(diǎn)間最短距離 A D B C E F 4 6 20 14 6 6 12 8 12 2 4 10 4 五、最短路徑 兩點(diǎn)間邊數(shù)最少的路徑 可用作交通自動(dòng)咨詢系統(tǒng) 兩點(diǎn)間邊權(quán)重的和最小的路徑 用來(lái)計(jì)算兩城市間路程最短， 時(shí)間最快，費(fèi)用最省的路徑 兩點(diǎn) A,B之間邊數(shù)最少的路徑 從 A點(diǎn)出發(fā)，對(duì)圖做廣度優(yōu)先遍歷。 (i,j)。 =v。i++) { u=GetVertex(G,i)。 MFSet T MFS。 } nodes[root2].parent=root1。} return 1。 int FindRoot(int i)。 } 樹(shù)的雙親表示法定義 template class T class PTree { PNodeT nodes[MAX_TREE_SIZE]。兩個(gè)結(jié)點(diǎn)各自所在分支的根相同，則他們處在同一分支，根不同，則所在分支不同。 2. 重復(fù) 1 n1次直到 T連通。lcloseEdge[j].lowcost) { closeEdge[j].lowcost=l。 cout“\n”v“ ”w“ ”lendl。 if(l0)closeEdge[i].lowcost=l。 closeEdge =new MiniCostEdgeInfo T [n]。 i = 0。i++) if(a[i].lowcost!=0amp。 }。( )) if (PathConnect(G,( ),( ))) { (( ))。 SeqListT markedList, scList, L。( )) (( ))。 SeqListT markedList, L。 ( )) cout ( ) 。 } } } return *L。 (beginVertex)。 SeqListT L,adjL。 if (!FindVertex(*L,vertex)) { (*L).Insert(vertex)。 GraphT::DepthFirstSearch(const Tamp。 L=new SeqListT。i++) visited[i]=0。 } template class T class VertexIterator: public SeqListIterator T { public: VertexIterator(Graph T amp。 } template class T int GraphT::FindVertex(SeqListT amp。 col pos。 for (row = pos + 1。 return。 if (pos1 == 1 || pos2 == 1) { cerr InsertEdge: a vertex is not in the graph. endl。 exit (1)。 } template class T int GraphT::GetNextNeighbor(const int v, const int v1) {if (v 0||vgraphsize ||v1 0||v1graphsize) { cerr “The vertex is not in the graph. endl。 ( )。 SeqListIteratorT viter(vertexList)。 vertex1, const Tamp。 while(!( ) amp。 f weight。 i nvertices。 T S1, S2。 i MaxGraphSize。 SeqListTamp。 // utility methods void ReadGraph(char *filename)。 void InsertEdge(const Tamp。 vertex2)。 int GetVertexPos(const Tamp。} }。 eVertex)。 SeqListTamp。 void DeleteEdge(const Tamp。 int GetNextNeighbor(const int v1, const int v2)。 int NumberOfVertices(void) const。 int FindVertex(SeqListT amp。 有向樹(shù) 有向圖連通圖恰有一個(gè)頂點(diǎn)的入度為 0， 其余頂點(diǎn)的入度都是 1。 v5 v1 v3 v2 v4 v5 v1 v3 v2 v4 弱連通 強(qiáng)連通 強(qiáng)連通分量：彼此強(qiáng)連通的頂點(diǎn)的子集 A C B D I E G F H ABC D EFG H I 完全圖 任意兩點(diǎn)間都有邊相關(guān)聯(lián)的圖。v j, 以 vi為起點(diǎn) vj為終點(diǎn)的頂點(diǎn)序列。 ID(vi): 入度 ，以 vi為終點(diǎn)的邊的數(shù)目。 簡(jiǎn)單圖 沒(méi)有自身環(huán)，兩點(diǎn)間至多一條邊 v5 v1 v1 v3 v2 v3 v4 v4 v2 無(wú)向圖 有向圖 圖的基本概念 G=V, E V={v1,v2, 網(wǎng)絡(luò) 有權(quán)圖 子圖 G=(V, E), G?=(V?, E?) 如果 V? V, E? E , 就稱(chēng) G?是 G的子圖。 A[i,j]=1 (vi,vj)∈ E =0 . v5