圖的生成樹和最小生成樹的概念

在一個連通圖G中，如果取它的全部頂點和一部分邊構成一個子圖G′，即：

V(G’)=V(G)和E(G’)ÍE(G)

若邊集E(G’)中的邊既能夠把圖中的所有頂點連通而又不形成回路，則稱子圖G’是原圖G的一棵生成樹（Spanning Tree）。

下面簡單說明一下既包含連通圖G中的全部n個頂點又沒有回路的子圖G’（即生成樹）必含有n-1條邊。要構造子圖G’，首先從圖G中任取一個頂點加入G’中，此時G’中隻有一個頂點，假定具有一個頂點的圖是連通的，以後每向G’中加入一個頂點，都要加入以該頂點為一個端點，以已連通的頂點之中的一個頂點為另一個端點的一條邊，這樣既連通了該頂點又不會産生回路，進行n-1次後，就向G’中加入了n-1個頂點和n-1條邊，使得G’中的n個頂點既連通又不産生回路。

在圖G的一棵生成樹G’中，若再增加一條邊，就會出現一條回路。這是因為此邊的兩個端點已連通，再加入此邊後，這兩個端點間有兩條路徑，因此就形成了一條回路，子圖G’也就不再是生成樹了。同樣，若從生成樹G’中删去一條邊，就使得G’變為非連通圖。這是因為此邊的兩個端點是靠此邊唯一連通的，删除此邊後，必定使這兩個端點分屬于兩個相互獨立的連通分量中，使G’變成了具有兩個獨立連通分量的非連通圖。

連通圖和它的生成樹

在這三棵生成樹中，圖7-11(b)所示的樹是從圖中頂點v₀出發利用深度優先搜索遍曆得到的，被稱之為深度優先生成樹；圖7-11(c)所示的樹是從頂點v₀出發利用廣度優先搜索遍曆得到的，被稱之為廣度優先生成樹；圖7-11(d)所示的樹是任意一棵生成樹。當然圖7-11(a)的生成樹遠不止這幾種，還可以畫出其他許多種。

對于一個連通網（即連通帶權圖，假定每條邊上的權均為大于零的實數）來說，生成樹不同，每棵樹的權（即樹中所有邊上的權值總和）也可能不同。圖7-12(a)就是一個連通網，圖7-12(b)、(c)、(d)是它的三棵生成樹，每棵樹的權都不同，分别為57、53和38。具有最小權的生成樹稱為圖的最小生成樹（Minimum Spanning Tree）。通過後面将要介紹的構造最小生成樹的算法可知，圖7-12(d)是圖7-12(a)的最小生成樹。

連通網和它的生成樹

求圖的最小生成樹很有實際意義。例如，若一個連通網表示城市之間的通訊系統，網的頂點代表城市，網的邊代表城市之間架設通訊線路的造價，各城市之間的距離不同，地理條件不同，其造價也不同，即邊上的權不同，現在要求既要連通所有城市、又要使總造價最低，這就是一個求圖的最小生成樹的問題。

求圖的最小生成樹的算法主要有兩個：一是普裡姆（Prim）算法。另一是克魯斯卡爾（Kruskal）算法。

圖的生成樹不唯一。因為同一個圖可以有不同的生成樹，隻要能夠連通所有頂點又不産生回路的任何子圖都是它的生成樹，如深度優先生成樹、廣度優先生成樹等。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!