算法基礎：

首先是prim算法三部曲：

（1）找到距離最小生成樹最近的節點。

（2）將距離最小生成樹最近的節點加入到最小生成樹中。

（3）更新非最小生成樹節點到最小生成樹的距離。

實現步驟：

首先我們利用一個for循環遍歷n - 1遍，因為我們從第1個節點開始將其加入到生成樹之中后知道添加到還剩兩個節點時，我們可以發現當我們添加玩倒數第二個節點后，最后一個節點的mindist數值在處理倒數第二個節點的第三部更新過程中已經得到了，這個距離不是倒數第二個節點到它的距離grid[cur][j]就是之前已經得到的它與某個節點之間的距離mindist[j]。

（1）尋找最近節點：

判斷最近節點的三個條件：1.未在生成樹中。 ?2.距離生成樹距離最短 ? ? 3.選取最短距離我們先隨便選出一個節點然后再與其他節點比較

if(!isvisited[j] && (cur = -1 || mindist[cur] < mindist[j]) ? ? ? ? ? ? ?Cur = j;

這里我們每遍歷一層就會將cur置為-1以便我們可以最快選取一個隨機節點并遍歷后面的節點與之比較。而第二層的mindist[j]的值已經在第一層的第三步更新操作中得到。

（2）將最近節點加入生成樹：

isintree[cur] = true;

（3）更新非生成樹節點到生成樹距離：

利用一個for循環遍歷所以非生成樹節點，并更新起距離mindist[j] < grid[cur][j] ? Mindist[j] = mindist[j] : mindist[j] = grid[cur][j]

#include<iostream>
#include<vector>
using?namespace?std;
int?main()?{
????int?v,?e;
????int?x,?y,?k;
????cin?>>?v?>>?e;
????//?填一個默認最大值，題目描述val最大為10000
????vector<vector<int>>?grid(v?+?1,?vector<int>(v?+?1,?10001));
????while?(e--)?{
????????cin?>>?x?>>?y?>>?k;
????????//?因為是雙向圖，所以兩個方向都要填上
????????grid[x][y]?=?k;
????????grid[y][x]?=?k;

????}
????//?所有節點到最小生成樹的最小距離
????vector<int>?minDist(v?+?1,?10001);

????//?這個節點是否在樹里
????vector<bool>?isInTree(v?+?1,?false);

????//?我們只需要循環?n-1次，建立?n?-?1條邊，就可以把n個節點的圖連在一起
????for?(int?i?=?1;?i?<?v;?i++)?{

????????// 1、prim三部曲，第一步：選距離生成樹最近節點
????????int?cur?=?-1;?//?選中哪個節點?加入最小生成樹
????????for?(int?j?=?1;?j?<=?v;?j++)?{?//?1?-?v，頂點編號，這里下標從1開始
????????????//??選取最小生成樹節點的條件：
????????????//??（1）不在最小生成樹里
????????????//??（2）距離最小生成樹最近的節點
????????????//??（3）只要不在最小生成樹里，先默認選一個節點?，在比較?哪一個是最小的
????????????//??理解條件3 很重要，才能理解這段代碼：(cur ==?-1 || minDist[j]?< minDist[cur])
????????????if?(!isInTree[j]?&&?(cur?==?-1?||?minDist[j]?<?minDist[cur]))?{
????????????????cur?=?j;
????????????}
????????}
????????// 2、prim三部曲，第二步：最近節點（cur）加入生成樹
????????isInTree[cur]?=?true;

????????// 3、prim三部曲，第三步：更新非生成樹節點到生成樹的距離（即更新minDist數組）
????????//?cur節點加入之后，?最小生成樹加入了新的節點，那么所有節點到?最小生成樹的距離（即minDist數組）需要更新一下
????????//?由于cur節點是新加入到最小生成樹，那么只需要關心與?cur?相連的?非生成樹節點?的距離?是否比?原來?非生成樹節點到生成樹節點的距離更小了呢
????????for?(int?j?=?1;?j?<=?v;?j++)?{
????????????//?更新的條件：
????????????//?（1）節點是?非生成樹里的節點
????????????//?（2）與cur相連的某節點的權值?比?該某節點距離最小生成樹的距離小
????????????//?很多錄友看到自己?就想不明白什么意思，其實就是?cur?是新加入?最小生成樹的節點，那么?所有非生成樹的節點距離生成樹節點的最近距離?由于?cur的新加入，需要更新一下數據了
????????????if?(!isInTree[j]?&&?grid[cur][j]?<?minDist[j])?{
????????????????minDist[j]?=?grid[cur][j];
????????????}
????????}
????}
????//?統計結果
????int?result?=?0;
????for?(int?i?=?2;?i?<=?v;?i++)?{?//?不計第一個頂點，因為統計的是邊的權值，v個節點有?v-1條邊
????????result?+=?minDist[i];
????}
????cout?<<?result?<<?endl;

}

leetcode - 1584:連接所有點的最小費用

就是利用題目中的公式建立鄰接矩陣在套用上面的模板即可：

class Solution {
public:
? ? int minCostConnectPoints(vector<vector<int>>& points) {
? ? ? ? int n = points.size();
? ? ? ? vector<vector<int>> grid(n, vector<int>(n, 0));
? ? ? ? // 計算任意兩點之間的曼哈頓距離并填充到grid矩陣中
? ? ? ? for(int i = 0; i < n; i++){
? ? ? ? ? ? for(int j = i + 1; j < n; j++){
? ? ? ? ? ? ? ? int x = abs(points[i][0] - points[j][0]);
? ? ? ? ? ? ? ? int y = abs(points[i][1] - points[j][1]);
? ? ? ? ? ? ? ? grid[i][j] = grid[j][i] = x + y;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? vector<bool> isvisited(n, false);
? ? ? ? vector<int> mindist(n, INT_MAX);
? ? ? ? mindist[0] = 0; // 從第一個點開始
? ? ? ? int res = 0;
? ? ? ? for(int i = 0; i < n - 1; i++){
? ? ? ? ? ? int cur = -1;
? ? ? ? ? ? // 選擇當前距離生成樹最近的節點
? ? ? ? ? ? for(int j = 0; j < n; j++){
? ? ? ? ? ? ? ? if(!isvisited[j] && (cur == -1 || mindist[j] < mindist[cur])){
? ? ? ? ? ? ? ? ? ? cur = j;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? isvisited[cur] = true;
? ? ? ? ? ? // 更新其他節點到生成樹的距離
? ? ? ? ? ? for(int j = 0; j < n; j++){
? ? ? ? ? ? ? ? if(!isvisited[j] && mindist[j] > grid[cur][j]){
? ? ? ? ? ? ? ? ? ? mindist[j] = grid[cur][j];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for(int i = 1; i < n; i++){
? ? ? ? ? ? res += mindist[i];
? ? ? ? }
? ? ? ? return res;
? ? }

?