prim算法精講
53. 尋寶（第七期模擬筆試）
題目描述：
在世界的某個區域，有一些分散的神秘島嶼，每個島嶼上都有一種珍稀的資源或者寶藏。國王打算在這些島嶼上建公路，方便運輸。
不同島嶼之間，路途距離不同，國王希望你可以規劃建公路的方案，如何可以以最短的總公路距離將所有島嶼聯通起來。
給定一張地圖，其中包括了所有的島嶼，以及它們之間的距離。以最小化公路建設長度，確保可以鏈接到所有島嶼。
輸入描述：
第一行包含兩個整數V和E，V代表頂點數，E代表邊數。頂點編號是從1到V。例如：V=2，一個有兩個頂點，分別是1和2。
接下來共有E行，每行三個整數v1，v2和val，v1和v2為邊的起點和終點，val代表邊的權值。
輸出描述：
輸出聯通所有島嶼的最小路徑總距離
輸入示例：
7 11
1 2 1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1
輸出示例：
6
解題思路
本題是最小生成樹的模板題，最小生成樹可以使用prim算法也可以使用kruskal算法計算出來。
最小生成樹是所有節點的最小連通子圖，即：以最小的成本（邊的權值）將圖中所有節點鏈接到一起。
圖中有n個節點，那么一定可以用n-1條邊將所有節點連接到一起。
那么如何選擇這n-1條邊就是最小生成樹算法的任務所在。
prim算法，是從節點的角度采用貪心的策略每次尋找距離最小生成樹最近的節點并加入到最小生成樹中。
prim三部曲
- 第一步，選距離生成樹最近節點
- 第二步，最近節點加入生成樹
- 第三步，更新非生成樹節點到生成樹的距離（即更新minDist數組）
“每次尋找距離最小生成樹最近的節點并加入到最小生成樹中”，就用到了minDist數組，minDist數組用來記錄每一個節點距離最小生成樹的最近距離。
初始狀態
minDist數組里的數值初始化為最大數，現在還沒有最小生成樹，默認每個節點距離最小生成樹是最大的，這樣后面我們在比較的時候，發現更近的距離，才能更新到minDist數組上。
第一步：選距離生成樹最近節點
選擇距離最小生成樹最近的節點，加入到最小生成樹，剛開始還沒有最小生成樹，所以隨便選一個節點加入就好
第二步：最近節點加入生成樹
此時節點1已經算最小生成樹的節點。
第三步：更新非生成樹節點到生成樹的距離（即更新minDist數組）
#include<iostream>
#include<vector>
#include<climits>using namespace std;
int main(){int v,e;cin>>v>>e;int x,y,k;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、第一步：選距離生成樹最近節點int cur=-1;// 選中哪個節點 加入最小生成樹int minVal=INT_MAX;for(int j=1;j<=v;j++){// 1 - v，頂點編號，這里下標從1開始// 選取最小生成樹節點的條件：// （1）不在最小生成樹里// （2）距離最小生成樹最近的節點if(!isInTree[j]&&minDist[j]<minVal){minVal=minDist[j];cur=j;}}//2、第二步：最近節點（cur）加入生成樹isInTree[cur]=true;//3、第三步：更新非生成樹節點到生成樹的距離（即更新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 res=0;for(int i=2;i<=v;i++){res+=minDist[i];}cout<<res<<endl;
}拓展
上面講解的是記錄了最小生成樹所有邊的權值，如果讓打印出來最小生成樹的每條邊呢？或者說要把這個最小生成樹畫出來呢？
此時有兩個問題：
- 1、用什么結構來記錄
- 2、如何記錄
如果記錄邊，其實就是記錄兩個節點就可以，兩個節點連成一條邊。
如何記錄兩個節點呢？
我們使用一維數組就可以記錄。parent[節點編號] = 節點編號，這樣就把一條邊記錄下來了。（當然如果節點編號非常大，可以考慮使用map）
minDist數組里記錄的其實也是最小生成樹的邊的權值。”
既然minDist數組記錄了最小生成樹的邊，是不是就是在更新minDist數組的時候，去更新parent數組來記錄一下對應的邊呢。
所以在prim三部曲中的第三步，更新parent數組，代碼如下：
for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];parent[j] = cur; // 記錄最小生成樹的邊 （注意數組指向的順序很重要）}
}如果?parent[cur] = j?這么寫，最后更新的邏輯是 parent[1] = 2, parent[1] = 3， parent[1] = 4，最后只能記錄節點1與節點4相連，其他相連情況都被覆蓋了。
如果這么寫?parent[j] = cur，那就是 parent[2] = 1, parent[3] = 1， parent[4] = 1 ，這樣才能完整表示出節點1與其他節點都是鏈接的，才沒有被覆蓋。
kruskal算法精講
53. 尋寶（第七期模擬筆試）
解題思路
prim 算法是維護節點的集合，而 Kruskal 是維護邊的集合。
kruscal的思路：
- 邊的權值排序，因為要優先選最小的邊加入到生成樹里
- 遍歷排序后的邊
- 如果邊首尾的兩個節點在同一個集合，說明如果連上這條邊圖中會出現環
- 如果邊首尾的兩個節點不在同一個集合，加入到最小生成樹，并把兩個節點加入同一個集合
而判斷兩個節點是否在同一個集合中，就用到了前面講的并查集；
#include<iostream>
#include<vector>
#include<algorithm>using namespace std;struct Edge{int l,r,val;
};
int n=10001;
vector<int> father(n,-1);void init(){for(int i=0;i<n;i++){father[i]=i;}
}
int find(int u){if(father[u]==u)return u;father[u]=find(father[u]);return father[u];
}
void join(int u,int v){u=find(u);v=find(v);if(u==v)return;father[v]=u;
}int main(){int v,e;cin>>v>>e;int x,y,k;vector<Edge> edges; int res=0;vector<vector<int>> grid(v+1,vector<int>(v+1,10001));while(e--){cin>>x>>y>>k;edges.push_back({x,y,k});}sort(edges.begin(),edges.end(),[](const Edge& a,const Edge& b){return a.val<b.val;});init();for(Edge edge:edges){int i=find(edge.l);int j=find(edge.r);if(i!=j){res+=edge.val;join(i,j);}}cout<<res<<endl;return 0;
}
)
