2.5　樹

2.5.1　樹的概念和基本性質

不包含圈的圖稱為無圈圖，連通的無圈圖稱為樹。在一棵樹中，任意兩個頂點均有唯一的路連接。樹中度為1的點稱為葉子;度大于1的點稱為分支點或內部點。每個連通分支都是樹的圖稱為森林。圖2-14給出了六個頂點的樹。

定理2-3　設G=（V，E），|V|=n，|E|=m，則下列各命題是等價的:

① G是連通的并且不含圈;

② G中無圈，且m=n-1;

③ G是連通的，且m=n-1;

④ G中無圈，但在G中任意兩點之間增加一條新邊，就得到唯一的一個圈;

⑤ G是連通的，但刪除G中任一條邊后，便不連通（n≥2），也即它的每條邊都是割邊;

⑥ G中任意兩個頂點之間均有唯一的路連接（n≥2）。

2.5.2　深度和寬度優先搜索

由前面可以看到，連通性是圖的基本屬性，但是怎樣確定一個圖是否是連通的呢?在圖的規模比較小的情況下，只需檢查所有頂點對之間是否有路徑。然而，在大規模的圖中，這種方法可能是耗時的，因為要檢查的路徑的數量可能是令人望而生畏的。因此，希望有一個既有效又適用于所有圖的系統的程序或算法。對G的一個子圖F，用?（F）表示關于F的邊割集。

令T是圖G的一棵樹，如果V（T）=V（G），那么T是G的一棵生成樹，于是G是連通的。但是如果V（T）?V（G），則會出現兩種可能:或者?（T）=?，在這種情況下，G是不連通的;或者?（T）≠?，在這種情況下，對任何邊xy∈?（T），其中x∈V（T）和y∈V（G）\V（T），通過添加頂點y和邊xy到T中得到的仍是G的一棵樹。

使用上面的想法，可以在G中生成一序列根樹，開始于單個根頂點r組成的平凡樹，并終止于一棵生成樹或與相關聯的邊割集是空的非生成樹。將這一過程稱為樹搜索。如果目標只是確定一個圖是否連通，任何樹搜索都可以做到。然而，使用特定的標準來確定這個順序的樹搜索可以提供圖結構的額外信息。例如，一個稱為廣度優先搜索的樹搜索可能會被用來尋找在圖上的距離，以社會關系網絡為例，利用廣度優先搜索算法，可以找出你和地球上某個人之間的距離。另一個深度優先搜索，可以找到一個圖的割點。

（1）深度優先搜索介紹

圖的深度優先搜索和樹的先序遍歷比較類似。它的思想是:假設初始狀態是圖中所有頂點均未被訪問，則從某個頂點v出發，首先訪問該頂點，然后依次從它的各個未被訪問的鄰接點出發深度優先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到。若此時尚有其他頂點未被訪問到，則另選一個未被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。顯然，深度優先搜索是一個遞歸的過程。

圖2-15（a）展示了一個連通圖的一棵深度優先搜索樹（加粗實線）。這棵樹中每個頂點v被標記為（f（v），l（v）），其中f（v）表示頂點v加入到這棵樹的時間，l（v）表示頂點v的所有鄰點都加入到這棵樹的時間。圖2-15（b）展示了這棵樹的另一種畫法。

（2）廣度優先搜索介紹

廣度優先搜索，又稱為“寬度優先搜索”，簡稱BFS。它的思想是:從圖中某頂點v出發，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發依次訪問它們的鄰接點，并使得先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。換句話說，廣度優先搜索遍歷圖的過程是以v為起點，由近至遠，依次訪問和v有路徑相通且路徑長度為1，2…的頂點。

圖2-16展示了一個連通圖的一棵廣度優先搜索樹（加粗實線），其中圖2-16（a）中頂點的標號表示它們加入這棵樹的時間，而圖2-16（b）中頂點的標號表示它們到根節點的距離。

2.5.3　最小生成樹

給定圖G=（V，E），令T_G是G的一棵生成樹，我們將T_G中的邊稱為樹枝;G中不在T_G中的邊稱為弦;T_G的所有弦的集合稱為生成樹的補。

通信網絡設計問題的要求是，由所有中心點和選擇建造的連線子集所構成的子圖應該連通。假設圖G的每條邊e有正費用c_e，且子圖的費用就是它的邊費用總和，那么問題可表述為:給定連通圖G，對每條邊e∈E給定正費用c_e，找到G的一個最小費用連通生成子圖。利用費用為正這個事實，可以證明最優子圖將是一種特殊類型。首先有下面的觀察結果。

引理2-1　G的邊e=uv是G的某個圈中的邊當且僅當G\e中有一條從u到v的路。

由此可得，如果從一個連通圖的某個圈中刪除一條邊，那么新的圖還是連通的，所以連接器問題的最優解將不含任何圈。因此可以通過解最小生成樹（MST）問題來求解連接器問題:給定連通圖G，對每條邊e∈E給定正費用c_e，找到G的一棵最小費用生成樹。

有令人驚訝的簡單算法能夠找到一棵最小生成樹，這里描述兩個這樣的算法，它們都是基于“貪婪”原則——即在每一步都做最節省的選擇。

（1）MST的Kruskal算法

保持G的一個生成森林H=（V，F），并且初始時取F=?。在每一步往F中加一條最小費用邊e?F并保持H是森林。當H是生成樹時停止。

（2）MST的Prim算法

保持一棵樹H=（V（H），T），對某個r∈V，取V（H）的初始集為{r}，而T的初始集為?。在每一步往T中添加一條不在T中的最小費用邊e使得H始終是一棵樹。當H是生成樹時停止。

樹是圖論中一個非常重要的概念，在計算機科學中有著非常廣泛的應用，例如現在計算機操作系統均采用樹形結構來組織文件和文件夾。