【文章內(nèi)容簡介】 template class T SeqListTamp。 GraphT::DFS( ) { int *visited=new int[graphsize]。 for(int i=0。igraphsize。i++) visited[i]=0。 SeqListT *L=new SeqListT。 *L=DFS(0,visited)。 delete[]visited。 return *L。 } template class T SeqListTamp。 GraphT::DFS(const int v, int *visited) { SeqListT*L。 T vertex=(v)。 L=new SeqListT。 visited[v]=1。 LInsert(vertex)。 int w=GetFirstNeighbor(v) while(w!=1) {if(!visited[w])DFS(w,visited)。 w=GetNextNeihbor(v,w)。 } return *L； } SeqListT L。 //輸出頂點 StackT S。 //存儲待算頂點 //深度優(yōu)先搜索 2 不用 遞歸 用 棧 D B C A E I F H F B A S L AF HE B IE B AFH D B AFHIE C AFHIEDB AFHIEDBC template class T SeqListT amp。 GraphT::DepthFirstSearch(const Tamp。 beginVertex) { StackT S。 SeqListT *L, adjL。 SeqListIteratorT iteradjL(adjL)。 T vertex。 L = new SeqListT。 (beginVertex)。 //深度優(yōu)先搜索 2 不用 遞歸 用 棧 while (!( )) {vertex = ( )。 if (!FindVertex(*L,vertex)) { (*L).Insert(vertex)。 adjL = GetNeighbors(vertex)。 (adjL)。 for(( )。!( )。( )) if (!FindVertex(*L,( ))) (( ))。 } } return *L。 // return list } D B C A E I F H 廣度優(yōu)先搜索 用 隊列 ABFCHEDI QueueT Q。 SeqListT L,adjL。 BF A Q L AB FCH ABF CHE ABFC HED ABFCH EDI ABFCHEDI template class T SeqList T amp。 Graph T ::BreadthFirstSearch( const T amp。 beginVertex) { Queue T Q。 SeqList T *L, adjL。 SeqListIterator T iteradjL(adjL)。 T vertex。 L = new SeqList T 。 (beginVertex)。 // initialize the queue while (!( )) { vertex = ( )。 if (!FindVertex(*L,vertex)) { (*L).Insert(vertex)。 adjL = GetNeighbors(vertex)。 (adjL)。 for(( )。!( )。( )) { if (!FindVertex(*L,( ))) (( ))。 } } } return *L。 } 四、無向圖的連通分量和生成樹 一個圖中互相連通的點的極大子集叫 連通分量 。 從一點出發(fā)，深度優(yōu)先或廣度優(yōu)先搜索到的子圖就是 連通分量。 從連通圖的任意一點出發(fā)，深度優(yōu)先搜索到的子圖也就是圖的生成樹，也叫 深度優(yōu)先生成樹 ；廣度優(yōu)先搜索到的生成樹，也叫廣度優(yōu)先生成樹 ； 非連通圖遍歷得到的是 生成森林： 從一點出發(fā)深度優(yōu)先搜索并標記，得到一棵樹，再繼續(xù)得到另一棵樹，直到取遍所有頂點。 template class T void PrintList(SeqListT amp。L) { SeqListIteratorT liter(L)。 for (( )。 !( )。 ( )) cout ( ) 。 } template class T int PathConnect (GraphT amp。G, T v, T w) { SeqListT L。 // find vertices connected to v L = (v)。 // is w is in the list, return TRUE if ((w)) return 1。 else return 0。 } template class T void UConnectedComponent (GraphT amp。G) { VertexIteratorT viter(G)。 SeqListT markedList, L。 for (( )。 !( )。 ( )) { if (!(( ))) { ( )。 L = (( ))。 SeqListIteratorT liter(L)。 for(( )。!( )。( )) (( ))。 PrintList(L)。 cout endl。 } } } 強連通分量：彼此強連通的頂點的子集 A C B D I E G F H ABC D EFG H I 做法：從一點 v0出發(fā)作深度優(yōu)先搜索，得到一個頂點序列 L。檢查 L上的點到 v0， 是否也連通，所有連通的點組成一個強連通分量。 重復著一過程，直到取遍所有頂點。 template class T void ConnectedComponent (GraphT amp。G) { VertexIteratorT viter(G)。 SeqListT markedList, scList, L。 for (( )。 !( )。 ( )) { if (!(( ))) { ( )。 L = (( ))。 SeqListIteratorT liter(L)。 for (( )。!( )。( )) if (PathConnect(G,( ),( ))) { (( ))。 (( ))。 } PrintList(scList)。 cout endl。 } } } 最小生成樹 Minimumcost Spanning Tree 帶權(quán)連通圖（網(wǎng)絡）中權(quán)值總和最小的生成樹叫 最小生成樹 例 連接所有 n個點的通訊網(wǎng)絡的最短線路。 Prim 普里姆算法 設 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. 重復 2，直至 U=V. 得到 T就是最小生成樹。 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] 紀錄每點到 U的最短距離 (點，距離 ) U中點距離為 0， 每加入一個新點， 數(shù)組更新一次 templateclass T struct MiniCostEdgeInfo { T adjvex。 int lowcost。 }。 template class T int operator(MiniCostEdgeInfoT a, MiniCostEdgeInfoT b) { return 。 } template class T int minimum(MiniCostEdgeInfoT *a,int n) { for(int i=0。in。i++) if(a[i].lowcost!=0) break。 int min=i。 for(i=min+1。in。i++) if(a[i].lowcost!=0amp。amp。a[i]a[min]) min=i 。 return min。 } 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 MiniSpanTreePrim(Graph T G) { int j,k,l,n=( )。 MiniCostEdgeInfo T * closeEdge。 closeEdge =new MiniCostEdgeInfo T [n]。 T s,w, v=GetVertex(G,0)。 closeEdge[0].lowcost=0。//起始點 v0加進 U for(int i=