一、樹

包含N個頂點的無向圖G稱為一棵樹，它滿足以下任意一個條件：
（1）圖G是連通的并且有N-1條邊。
（2）圖G是連通的并且不包含圈。
（3）圖G不包含圈并且有N-1條邊。
（4）圖G中任意兩個頂點之間有且只有一條路徑。
（5）圖G中任意一條邊都是橋，即去掉圖G中的任意一條邊都會使圖變得不連通。

上圖中第一顆樹是自由樹，因為很難看出樹根。通過把某個頂點設定為根，就可以得到樹的層次表示，稱為根數，如第二顆樹所示。

二、廣度優先搜索算法

以上圖為例，利用廣度優先搜索算法尋找該圖的包含某個頂點(例如頂點1)的連通片可以描述如下：
（1）以頂點1為初始頂點,這個頂點記為第L${}_0$層；
（2）第一步是找到頂點1的所有鄰居頂點，包括頂點2和3，把這兩個頂點記為第L${}_1$層；

（3）第二步是找到第L${}_1$層頂點的所有未在前面層中出現的鄰居,包括頂點4、5、7和8,把這4個頂點記為第L${}_2$層；

（4）第三步是找到第L${}_2$層頂點的所有未在前面層中出現的鄰居，包括項點6,把這一頂點記為第L${}_3$層；

（5）已經找不到第L${}_3$層頂點的所有未在前面層中出現的鄰居,算法終止。此時得到一個以頂點1為根的樹，包括上圖中的頂點及實線邊，稱為廣度優先搜索樹。如果把這些頂點之間原有的邊(上圖中的虛線邊)添加進來,就得到包含頂點1的連通片。
如果要找出一個圖中的所有的連通片，那么可采用如下方法：先選取該圖中的一個頂點x，用廣度優先搜索得到包含頂點x的連通片；再選取一個不包含在該連通片中的頂點Y,用廣度優先搜索得到包含頂點Y的連通片;如此下去,直至所得到的這些連通片包含了圖中所有的頂點。

三、最小生成樹

1、定義

如果一個連通圖本身不是樹，那么該圖也可以看做是在一個樹 的基礎上添加一些邊而形成的，這就是生成樹的概念。
一個頂點數目很大的圖，其生成樹的數目一般而言可能大得驚人。例如，一個頂點標志了標號的完全圖K${}_N$的生成樹個數${}_T$(K${}_N$)有如下的Caylay公式:
${}_T$(K${}_N$)=N${}^{N?2}$。
下圖為包含5個頂點的連通圖及4個生成樹。

將生成樹的概念推廣到加權無向圖，此時每個生成樹邊數雖然相同，但邊的權值不同。權值之和最小的生成樹稱為最小生成樹。
注意：最小生成樹可能不唯一。但是當一個連通圖中所有邊的權值都不相同時最小生成樹是唯一的。

2、兩個定理

定理1：連通圖的一個權值之和最小的一個連通子圖一定是連通圖的一個最小生成樹。
定理2：給定連通圖G=(V,E,W)并假設所有邊的權值互不相同,則有：
（1）最小生成樹的割性質:令S是圖G的任意頂點子集,S≠0(空集),S≠V。令邊e是一個端點在S中,另一端點在V-S中的最小權值邊。那么圖G的最小生成樹必然包含邊e。
（2）最小生成樹的圈性質:令C是圖G中的一個圈，并假設邊e是圈C中權值最大的一條邊，那么圖G的最小生成樹必然不包含邊e。

3、構造最小生成樹

構造最小生成樹有兩個經典的算法，Prim算法和Kruskal算法。這兩個算法在數據結構中很經典，這里不在講述。

總結

以上是生活随笔為你收集整理的生成树与最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。