自由樹是無環連通圖（沒有確定的根）（在自由樹中選擇壹個頂點作為根就成為普通樹）。
從根開始，為每個頂點（通常稱為樹中的節點）的子節點指定從左到右的順序，它將成為有序樹。
在圖的應用中，我們經常需要求給定圖的壹個子圖使它成為壹棵樹。
生成樹
生成樹
如果連通圖G的子圖是包含G的所有頂點的樹，則該子圖稱為G的生成樹。
生成樹是包含連通圖中所有頂點的最小連通子圖。
圖的生成樹不僅從不同的頂點開始遍歷，而且可以得到不同的生成樹。
深度優先生成樹和寬度優先生成樹
（）生成樹求解方法
設圖G =（V E）是具有n個頂點的連通圖，從G的任意頂點（源點）通過深度優先搜索（廣度優先搜索）對其進行搜索。
在搜索過程中，從訪問過的頂點v i搜索到未訪問過的相鄰點v j時經過的n個頂點和邊（V I V J）（* * * n條）。
的最小連通子圖是生成樹（源點是生成樹的根）
通常將深度優先搜索得到的生成樹簡稱為深度優先生成樹或DFS生成樹。通過廣度優先搜索得到的生成樹稱為廣度優先生成樹。
稱為BPS生成樹
例如，從圖G的頂點V獲得的DFS生成樹如下圖（a）所示。具體生成過程見下圖（b）所示的BFS生成樹動畫演示。
請參見體積生成過程的動畫演示。
（）求DFS生成樹和BFS生成樹的算法
只要在遞歸調用語句之前向DFS（或DFSM）算法的if語句添加適當生成邊（v i v j）的操作（例如輸出或保存邊），就可以獲得它。
尋找DFS生成樹的算法
在BFS（BFSM）算法的if語句中加入生成樹邊的操作，可以得到BFS生成樹的算法。參見練習。
註意
①圖的廣度優先生成樹的高度不會超過圖的其他生成樹的高度。
②圖的生成樹不僅從不同的頂點開始遍歷，而且可以得到不同的生成樹。
生成樹的壹般定義
如果從圖的某個頂點可以系統地訪問圖中的所有頂點，則由遍歷時經過的邊和圖的所有頂點組成的子圖稱為圖的生成樹（這
該定義不僅適用於無向圖，也適用於有向圖）
（）如果G是壹個強連通有向圖，則G中的所有頂點都可以從任意壹個頂點V訪問，這樣就可以得到以V為根的生成樹。
（）如果G是有根有向圖，根是V，則可以從根V開始完成G的遍歷，以獲得根為V的G的生成樹。
下圖中，（a）是壹個以V為根的有向圖，其DFS生成樹和BPS生成樹分別如圖（b）和（c）所示。
（）如果G是壹個不連通的無向圖，則必須從外部多次調用DFS（或BFS）算法才能完成對G的遍歷。每次外部調用只能訪問G中的壹個。
連通分量的頂點集這些頂點和它們穿過的邊構成了連通分量的DFS（或BPS）生成樹，以及g的每個連通分量的DFS（或BFS）生成
樹木組成了BFS森林。
（）如果G是非強連通有向圖，並且源點不是該有向圖的根，則遍歷時壹般只能得到該有向圖的生成森林。
例如，在下面的（a）所示的有向圖中，DFS和BFS跨越森林分別在（b）和（c）中示出。
Lishi Xinzhi/Article/program/sjjg/201311/23831