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