# 生成樹和最小生成樹 > 原文： [https://www.programiz.com/dsa/spanning-tree-and-minimum-spanning-tree](https://www.programiz.com/dsa/spanning-tree-and-minimum-spanning-tree) #### 在本教程中，您將通過示例和圖形學習有關生成樹和最小生成樹的信息。 在學習生成樹之前，我們需要了解兩個圖：無向圖和連接圖。 **無向圖**是其中邊沒有指向任何方向的圖（即，邊是雙向的）。  無向圖 **連通圖**是其中始終存在從頂點到任何其他頂點的路徑的圖。  連通圖 * * * ## 生成樹 生成樹是無向圖和連通圖的子圖，其中包括圖的所有頂點，這些頂點的邊數最少。 如果缺少頂點，則它不是生成樹。 邊可以分配權重，也可以不分配權重。 可以從完整圖形創建的具有`n`頂點的生成樹總數等于`n^(n-2)`。 如果我們有`n = 4`，則最大可能的生成樹數等于`4^(4-2) = 16`。 因此，可以從具有 4 個頂點的完整圖形中形成 16 個生成樹。 * * * ## 生成樹的示例 讓我們通過以下示例了解生成樹： 讓原始圖為：  普通的圖 可以從上圖創建的一些可能的生成樹是：  一棵生成樹  一棵生成樹  一棵生成樹  一棵生成樹  一棵生成樹  一棵生成樹 * * * ## 最小生成樹 最小生成樹是其中邊的權重之和盡可能最小的生成樹。 * * * ## 生成樹的示例 讓我們借助下面的示例了解上面的定義。 初始圖形為：  帶權圖 上圖可能的生成樹是：  最小生成樹 - 1  最小生成樹- 2  最小生成樹 - 3  最小生成樹 - 4 上述生成樹中的最小生成樹為：  最小生成樹 使用以下算法可找到圖中的最小生成樹： 1. [Prim 的算法](/dsa/prim-algorithm) 2. [Kruskal 算法](/dsa/kruskal-algorithm) * * * ## 生成樹應用 * 計算機網絡路由協議 * 聚類分析 * 民用網絡規劃 * * * ## 最小生成樹應用 * 在地圖中查找路徑 * 設計諸如電信網絡，供水網絡和電網的網絡。