最小生成樹的可以通過Kruskal(克魯斯卡爾)算法或Prim(普裡姆)算法求出。
Prim算法基本介紹：
Prim算法又稱為"加點法"，每次找出距離(此處的距離指的是距離最小生成樹的距離，若此處無法了解，可直接跳過，看完下面例子就能了解)最小的邊對應的點。算法逐漸從某一個頂點s開始，逐漸将n個點納入最小生成樹中。
Prim算法基本步驟：
第一步：設圖中所有頂點的集合為V，u代表已經加入最小生成樹的頂點的集合，v代表未加入最小生成樹的頂點的集合，最由于從某點s開始，是以u={s}，v={V-u}
第二步：在兩個集合u,v中選擇一條代價最小的邊，将在v中連接配接這條邊的那個頂點x加入到最小生成樹頂點集合u中，并且更新與x相連的所有鄰接點
第三步：重複上述步驟，直到最小生成樹頂點集合u中有n個頂點為止
Prim算法步驟示範，以下圖為例：min數組代表，每個頂點到最小生成樹的距離，以0為起點，0到最小生成樹的距離就為0
1.初始化：u={0}，v={1,2,3,4,5,6}，0加入到最小生成樹集合u中，将0設定為藍點，緊接着更新與0連接配接的鄰接點1和3，此時0是最小生成樹的一部分，1到最小生成樹的距離為8，3到最小生成樹的距離為5。
2.此時u={0}，v={1,2,3,4,5,6}，在u,v兩個集合中選擇一條代價最小的邊，下圖為例就是5，根據算法步驟，将在v中連接配接這條邊的頂點3加入到最小生成樹集合u中，此時u={0,3}，v={1,2,4,5,6}。然後更新與3連接配接的所有頂點到最小生成樹的距離，1到最小生成樹的距離更新為3，5到最小生成樹的距離更新為7，6到最小生成樹的距離更新為15
3.此時u={0,3}，v={1,2,4,5,6}，在u,v兩個集合中選擇一條代價最小的邊，下圖為例就是3，根據算法步驟，将在v中連接配接這條邊的頂點1加入到最小生成樹集合u中，此時u={0,3,1}，v={2,4,5,6}。然後更新與1連接配接的所有頂點到最小生成樹的距離，2到最小生成樹的距離更新為12，4到最小生成樹的距離更新為10
4.此時u={0,3,1}，v={2,4,5,6}，在u,v兩個集合中選擇一條代價最小的邊，下圖為例就是7，根據算法步驟，将在v中連接配接這條邊的頂點5加入到最小生成樹集合u中，此時u={0,3,1,5}，v={2,4,6}。然後更新與5連接配接的所有頂點到最小生成樹的距離，2到最小生成樹的距離更新為2，4到最小生成樹的距離更新為9
5.此時u={0,3,1,5}，v={2,4,6}，在u,v兩個集合中選擇一條代價最小的邊，下圖為例就是2，根據算法步驟，将在v中連接配接這條邊的頂點2加入到最小生成樹集合u中，此時u={0,3,1,5,2}，v={4,6}。然後更新與2連接配接的所有頂點到最小生成樹的距離，4到最小生成樹的距離更新為6
6.此時u={0,3,1,5,2}，v={4,6}，在u,v兩個集合中選擇一條代價最小的邊，下圖為例就是6，根據算法步驟，将在v中連接配接這條邊的頂點4加入到最小生成樹集合u中，此時u={0,3,1,5,2,4}，v={6}。然後更新與4連接配接的所有頂點到最小生成樹的距離，發現4沒有鄰接點可以更新
6.此時u={0,3,1,5,2,4}，v={6}，在u,v兩個集合中選擇一條代價最小的邊，下圖為例就是15，根據算法步驟，将在v中連接配接這條邊的頂點6加入到最小生成樹集合u中，此時u={0,3,1,5,2,4,6}，v={}。然後更新與6連接配接的所有頂點到最小生成樹的距離，發現6沒有鄰接點可以更新
Prim算法執行完成後得到的最小生成樹為：
最終，将min中的值進行求和，結果為0+3+2+5+6+7+15=38，是以MST的值為38。有興趣的朋友可以以此題為例，利用Kruskal算法求出最小生成樹😊😊。
你若盛開,蝴蝶自來;你若精彩,天自安排！算法學習貴在堅持，各位小夥伴們要堅持噢！如果對于以上博文有任何疑問，可以聯系本人。wechat：Q1313135😄