樹圖與最小生成樹

1、16.2 樹圖與最小生成樹樹圖與最小生成樹 一般研究無向圖一般研究無向圖 樹圖：倒置的樹，樹圖：倒置的樹，根根(root)在上，在上，樹葉樹葉(leaf)在下在下 多級輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分多級輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分類學(xué)、組織結(jié)構(gòu)等都是典型的樹圖類學(xué)、組織結(jié)構(gòu)等都是典型的樹圖C1C2C3C4根根葉葉2 6.2.1 樹的定義及其性質(zhì)樹的定義及其性質(zhì) 任兩點之間有且只有一條路徑的圖稱為任兩點之間有且只有一條路徑的圖稱為樹樹(tree)，記為，記為T 樹的性質(zhì)樹的性質(zhì)： 最少邊的連通子圖，樹中必不存在回路最少邊的連通子圖，樹中必不存在回路 任何樹必存在次數(shù)為任

2、何樹必存在次數(shù)為 1 的點的點 具有具有 n 個節(jié)點的樹個節(jié)點的樹 T 的邊恰好為的邊恰好為 n 1 條，反之，任何有條，反之，任何有n 個節(jié)點，個節(jié)點， n 1 條邊的連通圖必是一棵樹條邊的連通圖必是一棵樹 6.2.2 圖的生成樹圖的生成樹 樹樹 T 是連通圖是連通圖 G 的的生成樹生成樹(spanning tree)，若，若 T 是是 G的的子圖且包含圖子圖且包含圖 G 的所有的節(jié)點；包含圖的所有的節(jié)點；包含圖 G 中部分指定節(jié)中部分指定節(jié)點的樹稱為點的樹稱為 steiner tree 每個節(jié)點有唯一標(biāo)號的圖稱為標(biāo)記圖，標(biāo)記圖的生成樹每個節(jié)點有唯一標(biāo)號的圖稱為標(biāo)記圖，標(biāo)記圖的生成樹稱為稱為

3、標(biāo)記樹標(biāo)記樹(labeled tree)Caylay 定理定理：n ( 2)個節(jié)點，有個節(jié)點，有nn 2個不同的標(biāo)記樹個不同的標(biāo)記樹3 6.2.2 圖的生成樹圖的生成樹 如何找到一棵生成樹如何找到一棵生成樹 深探法深探法(depth first search)：任選一點標(biāo)記為：任選一點標(biāo)記為 0 點開始搜點開始搜索，選一條未標(biāo)記的邊走到下一點，該點標(biāo)記為索，選一條未標(biāo)記的邊走到下一點，該點標(biāo)記為 1，將，將走過的邊標(biāo)記；假設(shè)已標(biāo)記到走過的邊標(biāo)記；假設(shè)已標(biāo)記到 i 點，總是從最新標(biāo)記的點，總是從最新標(biāo)記的點向下搜索，若從點向下搜索，若從 i 點無法向下標(biāo)記，即與點無法向下標(biāo)記，即與 i 點相關(guān)聯(lián)

4、點相關(guān)聯(lián)的邊都已標(biāo)記或相鄰節(jié)點都已標(biāo)記，則退回到的邊都已標(biāo)記或相鄰節(jié)點都已標(biāo)記，則退回到 i 1 點繼點繼續(xù)搜索，直到所有點都被標(biāo)記續(xù)搜索，直到所有點都被標(biāo)記 廣探法廣探法(breadth first search)：是一種有層級結(jié)構(gòu)的搜索，：是一種有層級結(jié)構(gòu)的搜索，一般得到的是樹形圖一般得到的是樹形圖ACDBACDBACDBADCB4 6.2.3 最小生成樹最小生成樹 有有n 個鄉(xiāng)村，各村間道路的長度是已知的，如何敷設(shè)光個鄉(xiāng)村，各村間道路的長度是已知的，如何敷設(shè)光纜線路使纜線路使 n 個鄉(xiāng)村連通且總長度最短個鄉(xiāng)村連通且總長度最短 顯然，這要求在已知邊長度的網(wǎng)路圖中找最小生成樹顯然，這要求在已

5、知邊長度的網(wǎng)路圖中找最小生成樹 最小生成樹的算法最小生成樹的算法： Kruskal 算法：將圖中所有邊按權(quán)值從小到大排列，依算法：將圖中所有邊按權(quán)值從小到大排列，依次選所剩最小的邊加入邊集次選所剩最小的邊加入邊集 T，只要不和前面加入的邊，只要不和前面加入的邊構(gòu)成回路，直到構(gòu)成回路，直到 T 中有中有 n 1 條邊，則條邊，則 T 是最小生成樹是最小生成樹 Kruskal 算法基于下述定理算法基于下述定理定理定理 3 指定圖中任一點指定圖中任一點vi，如果，如果 vj 是距是距 vi 最近的相鄰節(jié)點，最近的相鄰節(jié)點，則關(guān)聯(lián)邊則關(guān)聯(lián)邊 eij 必在某個最小生成樹中。必在某個最小生成樹中。推論推論

6、 將網(wǎng)路中的節(jié)點劃分為兩個不相交的集合將網(wǎng)路中的節(jié)點劃分為兩個不相交的集合V1和和V2，V2=V V1，則，則V1和和V2間權(quán)值最小的邊必定在某個最小生間權(quán)值最小的邊必定在某個最小生成樹中。成樹中。5 6.2.3 最小生成樹最小生成樹 最小生成樹不一定唯一最小生成樹不一定唯一 定理定理 3 推論是一個構(gòu)造性定理，它指示了找最小生成樹推論是一個構(gòu)造性定理，它指示了找最小生成樹的有效算法的有效算法 Prim 算法：不需要對邊權(quán)排序，即可以直接在網(wǎng)路圖上算法：不需要對邊權(quán)排序，即可以直接在網(wǎng)路圖上操作，也可以在邊權(quán)矩陣上操作，后者適合計算機(jī)運算操作，也可以在邊權(quán)矩陣上操作，后者適合計算機(jī)運算 邊權(quán)矩

7、陣上的邊權(quán)矩陣上的 Prim 算法算法：1、根據(jù)網(wǎng)路寫出邊權(quán)矩陣，兩點間若沒有邊，則用、根據(jù)網(wǎng)路寫出邊權(quán)矩陣，兩點間若沒有邊，則用 表示；表示；2、從、從 v1 開始標(biāo)記，在第一行打開始標(biāo)記，在第一行打 ，劃去第一列；，劃去第一列；3、從所有打、從所有打 的行中找出尚未劃掉的最小元素，對該元素畫圈，的行中找出尚未劃掉的最小元素，對該元素畫圈，劃掉該元素所在列，與該列數(shù)對應(yīng)的行打劃掉該元素所在列，與該列數(shù)對應(yīng)的行打 ；4、若所有列都劃掉，則已找到最小生成樹、若所有列都劃掉，則已找到最小生成樹(所有畫圈元素所對應(yīng)所有畫圈元素所對應(yīng)的邊的邊)；否則，返回第；否則，返回第 3 步。步。該算法中，打該算法中，打 行對應(yīng)的節(jié)點在行對應(yīng)的節(jié)點在 V1中，未劃去的列在中，未劃去的列在 V2中中6 6.2.3 最小生成樹最小生成樹 97125 .19179810787111275 . 9165 .195 . 9101710111610 Prim算法是多項式算法算法是多項式算法 Prim算法可以求最大生成樹算法可以求最大生成樹 網(wǎng)路的邊權(quán)可以有多種解釋，如效率網(wǎng)路的邊權(quán)可以有多種解釋，