最小生成樹：就是生成樹里面最小的。
那么先講什么是生成樹：
生成樹必須具備的幾個條件：
1.是連通圖；
2.含有圖的所有頂點（n）;
3.只有n-1條邊；
4.任意加一邊構成環。
那生成樹有什么意義呢？舉個例子，假如現在n個村子，這n個村子之間 還沒通網絡，他們想要彼此之間通網，那么也就是需要把大家連在一個網絡里，也就是把每個村子當做頂點放在連通圖里。這樣子就解決問題了，但是這樣子的連通圖有很多個，每個村子之間可能會有很多條線，顯然會浪費，那么我們就要求只有n-1條網線。這就是生成樹。那問題來了，他們最后發現只有n-1條網線的方案也有很多種，他們想知道哪一種線路是總網線長度最短？這個時候他們想出來最小生成樹。
從上面我們可以得出最小生成樹的概念：
生成樹+路徑最短
這個時候我就很好奇，這些村民是怎么找出最小生成樹的呢？要把所有的生成樹畫出來后再計算嗎？
答案并不是的。他們發明了兩種算法：
**Kruskal算法：**就是把每個村的距離先寫出來，然后把最小距離的村子之間連起來，然后再看距離第二小的兩個村子，如果這兩個村子還沒連通，那么就把它們連起來，如果連通了就放棄，直接看距離第三小的兩個村子。就這樣子重復知道所有的頂點都連通。這是一個叫做克魯斯卡爾的村民提出來，所有叫克魯斯卡爾算法；
**Prim算法：**對，這是另一個村民提出來的算法，叫普里姆算法。這個算法是基于頂底。首先先選一個村子，然后算出其他相鄰的村子到這個村子的距離，把最短的村子連起來。然后再把這兩個村子看成 一個整體，看看其他的村子到這兩個村子的距離，然后再挑選最短的連起來。重復知道所有的村子都被連起來了。
這個時候有一個村長就說了，克魯斯卡爾和普里姆兩個人算出來的是同一個嗎？會不會出現兩種不同的方案？
確實，克魯斯卡爾算法和普里姆算法會有可能出現不同的最小生成樹。

總結

以上是生活随笔為你收集整理的*17.解释一下最小生成树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。