生成樹可以定義為連通的無向圖G的子圖，該圖是通過從圖中移除所需數量的邊而產生的樹。 換句話說，生成樹是連接和無向圖G的非迴圈子圖，其將所有頂點連接在一起。 圖G可以具有多個生成樹。
1. 最小生成樹
可以在加權圖中為每個邊分配權重。 但是，最小生成樹是具有最小總權重的生成樹。 換句話說，最小生成樹是在某個特定圖的所有其他生成樹中包含最小權重的生成樹。
2. 最短路徑演算法
在本教學的這一部分中，接下來將討論用於計算圖中兩個節點之間的最短路徑的演算法。
有兩種演算法可用於此目的：
上一篇：
深度優先搜索（DFS）演算法
下一篇：
線性搜索