最小支撐樹結(jié)構(gòu)介紹

最小支撐樹生成樹

由圖遍歷的過程中經(jīng)過的邊加上圖的所有頂點所構(gòu)成的子圖。

最小支撐樹生成樹的特點

（1）n個頂點的連通子圖的生成樹是一個極小連通子圖，它包含圖中所有頂點和n-1條邊（但有n-1條邊的圖不一定是生成樹）。

（2）生成樹中任意兩個頂點間的路徑是唯一的。

最小支撐樹樹的權(quán)

生成樹T各邊的權(quán)值總和稱為該樹的權(quán)。

最小支撐樹最小生成樹

將權(quán)最小的生成樹稱為圖的最小生成樹。

Krusal算法和Prim算法是兩個構(gòu)造最小生成樹的著名算法。

設(shè)為 N=(V,E,C)連通網(wǎng)，TE是N的最小支撐樹的邊的集合。

① 算法開始時， U= {u o }(u o ∈ V), TE= ○ ；

② 找到滿足

weight(u,v)=min{weight(u 1 ,v 1 )| u 1 ∈ U, v 1 ∈ V-U }, 的邊，把它并入集合

TE中，v同時并入U。

③ 反復(fù)執(zhí)行② ,直至 V=U 時終止算法。

普里姆算法執(zhí)行過程示例

由上述圖解算法的過程知，構(gòu)造的最小生成樹不一定唯一，但最小生成樹的權(quán)值之和一定是相同的 。

一個網(wǎng)絡(luò)圖可以有多個生成樹．記N的所有生成樹的集合為：

設(shè)

則稱 T * 為網(wǎng)絡(luò)N的一棵最小樹樹形圖，簡稱最小樹。

求最小樹的兩種方法，是避圈法與破圈法 。

最小樹形圖問題避圈法

從網(wǎng)絡(luò)圖中任意節(jié)點開始尋找與該節(jié)點關(guān)聯(lián)的權(quán)數(shù)最小的邊，使之與已選邊不構(gòu)成為圈，直到選夠n-1條邊為止。

最小樹形圖問題破圈法

① 在網(wǎng)絡(luò)圖中尋找一個圈。若不存在圈，則已經(jīng)得到最短樹或網(wǎng)絡(luò)不存在最短樹；

② 去掉該圈中權(quán)數(shù)最大的邊；

反復(fù)重復(fù) ① ② 兩步，直到最小樹。

最小樹形圖問題Kruskal 算法

將圖中所有邊按權(quán)值從小到大排列，依次選所剩最小的邊加入邊集 T，只要不和前面加入的邊構(gòu)成回路，直到 T 中有 n-1 條邊，則 T 是最小生成樹。

樹形圖的概念

無圈且連通的無向圖稱為樹。樹一般記為T。作為樹定義還可以有以下幾種表述：

(1) T 連通且無圈或回路；

(2) T 無圈且有n－1條邊（如果有n個結(jié)點）；

(3) T 連通有n－1條邊；

(4) T 無回路，但不相鄰的兩個結(jié)點之間聯(lián)以一邊，恰得一個圈；

(5) T 連通，但去掉T 的任意一條邊，T 就不連通了；（亦即在點集合相同的圖中，樹是含邊數(shù)最少的

連通圖。）

(6) T 的任意兩個結(jié)點之間恰有一條初等鏈。