【正文】 入邊數(shù)計數(shù) while ( count NumVertices ) { ( e )。 (e)。 = v。 v NumVertices。 u NumVertices。 //頂點數(shù) UFSets F ( NumVertices )。 //邊結點輔助單元 MinHeap MSTEdgeNode H( NumEdges )。 } 利用克魯斯卡爾算法建立最小生成樹 void Graphstring :: Kruskal ( MinSpanTreeamp。 } int Insert ( MSTEdgeNodeamp。 int MaxSize, n。 //生成樹各邊的權值 public: MSTEdgeNode ( ) //構造函數(shù) : tail ( 1 ), head ( 1 ), cost ( 0 ) { } }。 private: int tail, head。 應用克魯斯卡爾算法構造最小生成樹的過程 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 5 0 4 6 1 3 2 原圖 (a) (b) 10 12 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 5 0 4 6 1 3 2 10 14 12 原圖 (c) (d) 5 0 4 6 1 3 2 10 14 16 12 (e) (f) (g) 5 0 4 6 1 3 2 10 14 22 16 12 5 0 4 6 1 2 10 25 14 22 16 12 3 最小生成樹類定義 const int MAXNUM = 機器可表示的 , 問題中 不可能出現(xiàn)的大數(shù) class MinSpanTree。 ? 首先 , 利用最小堆來存放 E中的所有的邊 , 堆中每個結點的格式為 ? 在構造最小生成樹過程中 , 利用并查集的運算檢查依附一條邊的兩頂點 tail、 head 是否在同一連通分量 (即 并查集的同一個子集合 ) 上 , 是則舍去這條邊；否則將此邊加入 T, 同時將這兩個頂點放在同一個連通分量上。 如此重復下去 , 直到所有頂點在同一個連通分量上為止。當在 E 中選到一條具有最小權值的邊時 , 若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到 T 中 。 ? 構造最小生成樹的準則 ? 必須使用且僅使用該網絡中的 n1 條邊來聯(lián)結網絡中的 n 個頂點； ? 不能使用產生回路的邊； ? 各邊上的權值的總和達到最小。 A B C D E F G H I J A B C D E F G H J A B C D E F G H J I I 1 2 3 4 5 6 7 8 9 10 根有兩 個子女 關節(jié)點 關節(jié)點 關節(jié)點 最小生成樹 ( minimum cost spanning tree ) ? 使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。 ? 深度優(yōu)先生成樹的根是 關節(jié)點 的充要條件是 它至少有兩個子女 。 ? 在一個無向連通圖 G中 , 重連通分量可以利用深度優(yōu)先生成樹找到。 ? 在重連通圖上 , 任何一對頂點之間至少存在有兩條路徑 , 在刪去某個頂點及與該頂點相關聯(lián)的邊時 , 也不破壞圖的連通性。 //取 v 的下一個鄰接頂點 w } //回到 while 判鄰接頂點 w 存在 } 重連通分量 (Biconnected Component) ? 在無向連通圖 G中 , 當且僅當刪去 G中的頂點 v及 所有依附于 v的所有邊 后 , 可將圖分割成兩個或兩個以上的連通分量，則稱頂點 v為 關節(jié)點 。 // p 插入為 p 的左子女 DFS_Tree ( T, p, w, visited )。 // p 插入為 RT 的左子女 FirstChild = 0。 //取頂點 v 的第一個鄰接頂點 w int FirstChild = 1。 visited [v] = 1。 //從頂點 i 出發(fā)深度優(yōu)先遍歷 , 建立以 // subT為根的 T 的子樹 } } templateclass Type void Graph Type :: DFS_Tree ( TreeType amp。 //頂點 i 的值成為根 rt 的值 else subT = ( subT, GetValue(i) )。 i n。 i++ ) visited [i] = 0。 //創(chuàng)建訪問數(shù)組 for ( int i = 0。T ) { TreeNode Type * rt, * subT。 A B C D E F G A A B D E C F G 有向圖 深度優(yōu)先生成森林 delete [ ] visited。 //未訪問 , 出發(fā)訪問 OutputNewComponent ( )。 i NumVertices。 i++ ) visited[i] = 0。 for ( int i = 0。 ? 對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林 。 ? 若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷 , 可求得無向圖的所有連通分量。 } //重復檢測 v 的所有鄰接頂點 } //外層循環(huán)，判隊列空否 delete [ ] visited。 (w)。 while ( w != 1 ) { //若鄰接頂點 w 存在 if ( !visited[w] ) { //未訪問過 cout GetValue (w) ? ?。 ( )。 (v)。 visited[v] = 1。 //visited初始化 cout GetValue (v) 39。 i NumVertices。 圖的廣度優(yōu)先搜索算法 templateclass Type void Graph Type :: BFS ( int v ) { int * visited = new int[NumVertices]。 ? 為了實現(xiàn)逐層訪問 , 算法中使用了一個 隊列 ,以記憶正在訪問的這一層和上一層的頂點 ,以便于向下一層訪問。 ? 廣度優(yōu)先搜索是一種分層的搜索過程 , 每向前走一步可能訪問一批頂點 , 不像深度優(yōu)先搜索那樣有往回退的情況。 //取頂點 v 排在 w 后的下一個鄰接頂點 } } 廣度優(yōu)先搜索 BFS ( Breadth First Search ) ? 廣度優(yōu)先搜索的示例 A C D E G B F I H A C D E G B F H 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹 I ? BFS在訪問了 起始頂點 v 之后 , 由 v 出發(fā) , 依次訪問 v 的各個 未被訪問過的鄰接頂點 w1, w2, …, wt, 然后再順序訪問 w1, w2, …, wt 的所有還未被訪問過的鄰接頂點。 //取 v 的第一個鄰接頂點 w while ( w != 1 ) { //若鄰接頂點 w 存在 if ( !visited[w] ) DFS ( w, visited )。 //訪問頂點 v visited[v] = 1。 //從頂點 0出發(fā)開始搜索 delete [ ] visited。 i++ ) visited [i] = 0。 for ( int i = 0。重復上述過程 , 直到連通圖中所有頂點都被訪問過為止。 如果有 , 則訪問此頂點 , 之后再從此頂點出發(fā) , 進行與前述類似的訪問 。 然后再從 w2 出發(fā) , 進行類似的訪問 , … 如此進行下去 , 直至到達所有的鄰接頂點都被訪問過的頂點 u 為止 。 ? 圖的遍歷的分類 : ? 深度優(yōu)先搜索 DFS (Depth First Search) ? 廣度優(yōu)先搜索 BFS (Breadth First Search) 深度優(yōu)先搜索 DFS ( Depth First Search ) ? 深度優(yōu)先搜索的示例 A C D E G B F I H A C D E G B F I H 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 前進 回退 深度優(yōu)先搜索過程 深度優(yōu)先生成樹 ? DFS 在訪問圖中某一起始頂點 v 后 , 由 v 出發(fā) , 訪問它的任一鄰接頂點 w1。 ? 為了避免重復訪問，可設置一個標志頂點是否被訪問過的輔助數(shù)組 visited [ ]。 –鄰接多重表的結構 mark vtx1 vtx2 path1 path2 ? ? ? ? ? ? ? ? ? ? 0 1 0 3 1 2 2 3 3 4 4 0 e1 e2 e3 e4 e5 e6 data Fin Fout A B C D E 0 1 2 3 4 e1 e2 e3 e4 e5 e6 A B C D E 圖的遍歷與連通性 ? 從已給的連通圖中某一頂點出發(fā)，沿著一 些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷 ( Graph Traversal )。 data Firstin Firstout path1是指向始頂點與該邊相同的下一條邊的指針； path2是指向終頂點與該邊相同的下一條邊的指針。 ? 邊結點的結構 mark vertex1 vertex2 path1 path2 其中， mark是處理標記； vertex1和 vertex2指明該有向邊始頂點和終頂點的位置。 ? 有向圖的情形 ? 在用鄰接表表示有向圖時 , 有時需要同時使用鄰接表和逆鄰接表。 data Firstout 需要時還可設置一個存放與該邊相關的權值的域 cost。 ?頂點結點的結構 存儲頂點信息的結點表 以順序表方式組織 , 每一個頂點結點有兩個數(shù)據(jù)成員：其中，data 存放與該頂點相關的信息， Firstout 是指示第一條依附該頂點的邊的指針。 vertex1和 vertex2是該邊兩頂點位置。為有關邊的處理提供了方便。 } } return 0。 while ( p != NULL ) { if ( pdest == v2 ) return pcost。amp。 } } return 1。 plink != NULL ) return plin