【正文】 同一分支，根不同，則所在分支不同。 同一分支的結(jié)點(diǎn)聯(lián)成一棵樹。 C B E A F D 問題： 分支？ ？ 并查集 MFS方法 問題： 分支？ 用 雙親表示法 表示結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都有一個(gè)數(shù)據(jù)和一個(gè)指向雙親的地址的指針。 重復(fù)以下步驟，直至 T連通： 取出最小邊，判斷這條邊的兩個(gè)端點(diǎn)，如果屬于T的不同的連通分支，加入 T, 把兩分支聯(lián)成一個(gè)。 2. 重復(fù) 1 n1次直到 T連通。 } Kruskal 克魯斯卡爾算法 G=(V,E) 連通圖 令 T=(V,{ }) 是 G的所有頂點(diǎn)而無邊的非連通圖。 ConnectedComponent(G)。 } } } } void main( ) { Graphchar G。lcloseEdge[j].lowcost) { closeEdge[j].lowcost=l。 if(l0amp。j++) //更新 closeEdge { v=GetVertex(G,j)。 //將 w加進(jìn) U for( j=0。 cout“\n”v“ ”w“ ”lendl。//取出這一邊 w=GetVertex(G,k)。i++) //雙重循環(huán)復(fù)雜度 O(n2)與邊數(shù)無關(guān) { k=minimum(closeEdge,n)。 } for( i=1。 if(l0)closeEdge[i].lowcost=l。 l=(v,w)。in。 closeEdge[0].lowcost=0。 closeEdge =new MiniCostEdgeInfo T [n]。 } templateclass T void MiniSpanTreePrim(Graph T G) { int j,k,l,n=( )。 ( )。amp。 i = 0。 return 0。 } templateclass T T GetVertex(GraphT G,int pos) { int i, n=( )。a[i]a[min]) min=i 。i++) if(a[i].lowcost!=0amp。 for(i=min+1。i++) if(a[i].lowcost!=0) break。 } template class T int minimum(MiniCostEdgeInfoT *a,int n) { for(int i=0。 }。 T中共有 n1條邊 D B C A E F H 10 28 25 22 12 16 18 14 24 D B C A E F H 10 28 25 22 12 16 18 14 24 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 U={A}, T={(A,C)} U={A,C}, T={(A,C),(C,F)} U={A,C,F}, T={(A,C),(C,F),(D,F)} U={A,C,F,D}, T={(A,C),(C,F),(D,F),(B,C)} U={A,C,F,D,B}, T={(A,C),(C,F),(D,F),(B,C),(B,E)} U={A,C,F,D,B,E} C B E A F D 6 5 3 6 4 5 2 1 5 6 A B C D E F U T 0 A 6 A 1 A 5 A (A,C) C 5 0 C 6 C 4 C (C,F) C 5 F 2 C 6 0 F (D,F) 0 D (B,C) 0 B 3 B (B,E) 0 E 定義數(shù)組 closeEdge[n] 紀(jì)錄每點(diǎn)到 U的最短距離 (點(diǎn)，距離 ) U中點(diǎn)距離為 0， 每加入一個(gè)新點(diǎn)， 數(shù)組更新一次 templateclass T struct MiniCostEdgeInfo { T adjvex。 } } } 最小生成樹 Minimumcost Spanning Tree 帶權(quán)連通圖（網(wǎng)絡(luò)）中權(quán)值總和最小的生成樹叫 最小生成樹 例 連接所有 n個(gè)點(diǎn)的通訊網(wǎng)絡(luò)的最短線路。 } PrintList(scList)。( )) if (PathConnect(G,( ),( ))) { (( ))。 for (( )。 L = (( ))。 !( )。 SeqListT markedList, scList, L。 template class T void ConnectedComponent (GraphT amp。檢查 L上的點(diǎn)到 v0， 是否也連通，所有連通的點(diǎn)組成一個(gè)強(qiáng)連通分量。 cout endl。( )) (( ))。 for(( )。 L = (( ))。 !( )。 SeqListT markedList, L。 } template class T void UConnectedComponent (GraphT amp。 // is w is in the list, return TRUE if ((w)) return 1。G, T v, T w) { SeqListT L。 ( )) cout ( ) 。 for (( )。 template class T void PrintList(SeqListT amp。 從一點(diǎn)出發(fā)，深度優(yōu)先或廣度優(yōu)先搜索到的子圖就是 連通分量。 } } } return *L。!( )。 (adjL)。 if (!FindVertex(*L,vertex)) { (*L).Insert(vertex)。 (beginVertex)。 T vertex。 SeqList T *L, adjL。 Graph T ::BreadthFirstSearch( const T amp。 SeqListT L,adjL。 } } return *L。!( )。 (adjL)。 if (!FindVertex(*L,vertex)) { (*L).Insert(vertex)。 (beginVertex)。 T vertex。 SeqListT *L, adjL。 GraphT::DepthFirstSearch(const Tamp。 //輸出頂點(diǎn) StackT S。 w=GetNextNeihbor(v,w)。 LInsert(vertex)。 L=new SeqListT。 GraphT::DFS(const int v, int *visited) { SeqListT*L。 return *L。 *L=DFS(0,visited)。i++) visited[i]=0。 for(int i=0。 G): SeqListIterator T () {} 深度優(yōu)先搜索 用 遞歸算法 ABCDEIHF D B C A E I F H 三、圖的遍歷 輸出頂點(diǎn)并標(biāo)記 循環(huán)： { 遞歸計(jì)算第一個(gè)鄰接點(diǎn) （如 未標(biāo)記） 下一個(gè)鄰接點(diǎn) } template class T SeqListTamp。 }。 } template class T class VertexIterator: public SeqListIterator T { public: VertexIterator(Graph T amp。 } ( )。 while(!( )) { if (( ) == vertex) { ret = 1。 vertex) { SeqListIteratorT iter(L)。 } template class T int GraphT::FindVertex(SeqListT amp。 return。 vertex2) { int pos1=GetVertexPos(vertex1), pos2=GetVertexPos(vertex2)。 } template class T void GraphT::DeleteEdge(const Tamp。 col pos。row graphsize。col++) edge[row1][col1] = edge[row][col]。row++) for (col = pos + 1。 for (row = pos + 1。col graphsize。 row pos。 graphsize。 return。 int row, col。 如果在表中，確定位置 pos 把鄰接矩陣分成四塊 I II III IV pos pos 第 I塊中邊不動 第 II塊中邊列左移 第 III塊中邊行上移 第 IV塊中邊 列左移行上移 template class T void GraphT::DeleteVertex(const Tamp。 } edge[pos1][pos2] = weight。 if (pos1 == 1 || pos2 == 1) { cerr InsertEdge: a vertex is not in the graph. endl。 vertex1, const Tamp。 在圖中，則確定位置 pos1,pos2， 設(shè)置邊（ pos1,pos2)的權(quán)值。 graphsize++。 exit (1)。 } template class T void GraphT::InsertVertex(const Tamp。 i++） if(edge[v][i] 0) return i。 } for(int i = v1+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。 i++) if(edge[v][i] 0) return i。 } for(int i = 0。 } template class T int GraphT::GetFirstNeighbor(const int v) {if (v 0||vgraphsize) { cerr “The vertex is not in the graph. endl。 ( )。 i graphsize。 return *L。 int pos = GetVertexPos(vertex)。 SeqListIteratorT viter(vertexList)。 GraphT::GetNeighbors(const Tamp。 } return ed