【正文】 678 MSTEdgeNodeT, E ed。 include include template class T, class E void Kruskal (GraphT, Eamp。 14677 ? 在求解最小生成樹時，可以用鄰接矩陣存儲圖，也可以用鄰接表存儲圖。 item)。 //最大元素個數(shù)和當前個數(shù) public: MinSpanTree (int sz = DefaultSize1) : MaxSize (sz), n (0) { edgevalue = new MSTEdgeNodeT, E[sz]。 template class T, class E 14676 class MinSpanTree { //樹的類定義 protected: MSTEdgeNodeT, E *edgevalue。 //兩頂點位置 E cost。 邊的兩個頂點位置 邊的權(quán)值 tail head cost 14673 ? 隨著各邊逐步加入到最小生成樹的邊集合中 , 各連通分量也在逐步合并 , 直到形成一個連通分量為止。 14672 ? 算法的框架 利用 最小堆 (MinHeap)和 并查集(DisjointSets)來實現(xiàn) 克魯斯卡爾算法 。 否則放棄 (v, w)。 從 E 中刪去 (v, w)。amp。 14671 Kruskal算法的偽代碼描述 T = ?。 否則將此邊舍去，重新選擇一條權(quán)值最小的邊。 北京 天津 南京 上海 廣州 西安 成都 昆明 武漢 34 7 6 41 58 31 24 19 25 38 22 22 19 31 39 44 50 14669 北京 天津 南京 上海 廣州 西安 成都 昆明 武漢 7 6 24 19 22 22 19 31 北京 天津 南京 上海 廣州 西安 成都 昆明 武漢 34 7 6 41 58 31 24 19 25 38 22 22 19 31 39 44 50 14670 克魯斯卡爾 (Kruskal) 算法 ? 克魯斯卡爾算法的基本思想： 設(shè)有一個有 n 個頂點的連通網(wǎng)絡(luò) N = { V, E }, 最初先構(gòu)造一個只有 n 個頂點 , 沒有邊的非連通圖 T = { V, ? }, 圖中每個頂點自成一個連通分量。 ? 構(gòu)造最小生成樹 假設(shè)有一個網(wǎng)絡(luò)，用以表示 n 個城市之間架設(shè)通信線路，邊上的權(quán)值代表架設(shè)通信線路的成本。 14666 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 根有兩 個子女 關(guān)節(jié)點 關(guān)節(jié)點 關(guān)節(jié)點 14667 最小生成樹 ( minimum cost spanning tree ) ? 使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。 ? 深度優(yōu)先生成樹的 根是 關(guān)節(jié)點 的充要條件是它至少有兩個子女 。 ? 在一個無向連通圖 G中 , 重連通分量可以利用深度優(yōu)先生成樹找到。 ? 在重連通圖上 , 任何一對頂點之間至少存在有兩條路徑 , 在刪去某個頂點及與該頂點相關(guān)聯(lián)的邊時 , 也不破壞圖的連通性。 14657 A C D E B F G O I H J N M L K 非連通無向圖 A H K C D E I B F O G J N M L 非連通圖的連通分量 14664 重連通分量 (Biconnected Component) ? 在無向連通圖 G中 , 當且僅當刪去 G中的頂點 v及所有依附于 v的所有邊后 , 可將圖分割成兩個或兩個以上的連通分量，則稱頂點 v為 關(guān)節(jié)點 。 ? 若從無向圖每一連通分量中的一個頂點出發(fā)進行遍歷 , 可求得無向圖的所有連通分量。 }。 //頂點 w進隊列 } w = (loc, w)。 //訪問 visited[w] = true。 //第一個鄰接頂點 while (w != 1) { //若鄰接頂點 w存在 if (!visited[w]) { //若未訪問過 14655 cout (w) 39。 //頂點進隊列 , 實現(xiàn)分層訪問 while (!() ) { //循環(huán) , 訪問所有結(jié)點 (loc)。 //做已訪問標記 Queueint Q。 39。 int loc = (v)。 i n。 //圖中頂點個數(shù) 圖的廣度優(yōu)先搜索算法 14654 bool *visited = new bool[n]。 G, const Tamp。 ? 為避免重復(fù)訪問 , 需要一個輔助數(shù)組 visited [ ]，給被訪問過的頂點加標記。因此 , 廣度優(yōu)先搜索不是一個遞歸的過程。再從這些訪問過的頂點出發(fā)，再訪問它們的所有還未被訪問過的鄰接頂點， … 如此做下去，直到圖中所有頂點都被訪問到為止。 //下一個鄰接頂點 } }。 //第一個鄰接頂點 while (w != 1) { //若鄰接頂點 w存在 if ( !visited[w] ) DFS(G, w, visited)。 //訪問頂點 v visited[v] = true。 G, int v, bool visited[]) { cout (v) 39。 //釋放 visited }。 DFS (G, loc, visited)。 i++) visited [i] = false。 //創(chuàng)建輔助數(shù)組 for (i = 0。 v) { //從頂點 v出發(fā)對圖 G進行深度優(yōu)先遍歷的主過程 int i, loc, n = ()。 14649 圖的深度優(yōu)先搜索算法 templateclass T, class E void DFS (GraphT, Eamp。 如果沒有 , 就再退回一步進行搜索。 接著 , 退回一步 , 退到前一次剛訪問過的頂點 , 看是否還有其它沒有被訪問的鄰接頂點。 再從 w1 出發(fā) , 訪問與 w1鄰 接 但還 沒有訪問過的頂點 w2。 14646 ? 輔助數(shù)組 visited[ ]的初始狀態(tài)為 0, 在圖的遍歷過程中 , 一旦某一個頂點 i 被訪問 , 就立即讓 visited[i]為 1, 防止它被多次訪問。 ? 圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。 mark vertex1 vertex2 path1 path2 14643 ? 頂點結(jié)點的結(jié)構(gòu) ? 每個頂點有一個結(jié)點，它相當于出邊表和入邊表的表頭結(jié)點：其中，數(shù)據(jù)成員 data存放與該頂點相關(guān)的信息，指針 Firstin 指示以該頂點為始頂點的出邊表的第一條邊， Firstout 指示以該頂點為終頂點的入邊表的第一條邊。 path1是指向 始頂點與該邊相同 的下一條邊的指針；path2是指向 終頂點與該邊相同 的下一條邊的指針。用有向圖的鄰接多重表(十字鏈表 )可把兩個表結(jié)合起來表示。 data Firstout 14641 mark vtx1 vtx2 path1 path2 ? ? ? ? 0 1 0 2 1 3 e1 e2 e3 data Fout A B C D 0 1 2 3 e1 e2 e3 A B C D ? 從頂點 i 出發(fā) , 可以循鏈找到所有依附于該頂點的邊，也可以找到它的所有鄰接頂點。 ? 頂點結(jié)點的結(jié)構(gòu) ? 頂點信息的結(jié)點表以順序表方式組織 , 每一個頂點結(jié)點有兩個數(shù)據(jù)成員：其中， data 存放與該頂點相關(guān)的信息， Firstout 是指示第一條依附該頂點的邊的指針。 path1域是鏈接指針 , 指向下一條依附頂點 vertex1的邊； path2 是指向下一條依附頂點 vertex2的邊鏈接指針。 ? 無向圖的情形 ? 邊結(jié)點的結(jié)構(gòu) ? 其中 , mark 是記錄是否處理過的標記 。 14639 鄰接多重表 (Adjacency Multilist) ? 在鄰接多重表中 , 每一條邊只有一個邊結(jié)點。 //返回下一個鄰接頂點 } return 1。amp。 pdest != w) p = plink。 while (p != NULL amp。 //第一個鄰接頂點不存在 }。 //對應(yīng)邊鏈表第一個邊結(jié)點 if (p != NULL) return pdest。 //刪除頂點表數(shù)組 }。 p = NodeTable[i].adj。 while (p != NULL) { NodeTable[i].adj = plink。 i numVertices。 }。 i maxVertices。 exit(1)。 NodeTable = new VertexT, E[maxVertices]。 numVertices = 0。 }。 int getFirstNeighbor (int v)。 bool insertEdge (int v1, int v2, E cost)。 vertex)。 } E getWeight (int v1, int v2)。amp。 //構(gòu)造函數(shù) ~Graphlnk()。 return 1。 i numVertices。 //輸出 14633 private: VertexT, E *NodeTable。 out, GraphlnkT, Eamp。 //輸入 friend ostreamamp。 in, GraphlnkT, Eamp。 template class T, class E class Graphlnk : public GraphT, E { //圖的類定義 friend istreamamp。 //頂點的名字 EdgeT, E *adj。 } //判邊等否 }。 //下一條邊鏈指針 Edge () {} //構(gòu)造函數(shù) Edge (int num, E cost) //構(gòu)造函數(shù) : dest (num), weight (cost), link (NULL) { } bool operator != (EdgeT, Eamp。 //邊的另一頂點位置 E cost。此外，把同一個頂點的所有邊鏈接在一個單鏈表中，也使得圖的操作更為便捷。 ? 設(shè)圖中有 n 個頂點， e 條邊，則用鄰接表表示無向圖時，需要 n 個頂點結(jié)點， 2e 個邊結(jié)點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需 n 個頂點結(jié)點， e 個邊結(jié)點。 14628 data adj A B C 0 1 2 dest link dest link ? 鄰接表 (出邊表 ) data adj A B C 0 1 2 dest link 逆鄰接表 (入邊表 ) 1 0 2 ? ? ? ? ? 0 1 1 有向圖的鄰接表和逆鄰接表 A B C 14629 B A C D 6 9 5 2 8 data adj A B C D 0 1 2 3 dest cost link ? ? ? ? 1 5 3 6