f678 - FJCU_109_Winter_Day3_Lab2 最小生成樹練習
題目描述
題目要求給定一張包含 N 個頂點和 M 條邊的加權無向圖，計算其最小生成樹 (Minimum Spanning Tree, MST) 的總權重。
解題思路
本題採用 Prim's Algorithm 解決。Prim's Algorithm 是一種貪心演算法，用於在加權連通無向圖中找到最小生成樹。其基本思想是從一個起始頂點開始，逐步擴展生成樹，每次選擇與當前生成樹連接且權重最小的邊。
程式碼中，adj[i][j] 儲存頂點 i 到頂點 j 的權重，初始值為一個很大的數字 (1e9) 表示沒有邊。然後，根據輸入讀取邊的資訊，更新 adj 矩陣。d[i] 記錄從已建立的 MST 到頂點 i 的最小距離。visit[i] 記錄頂點 i 是否已經包含在 MST 中。
Prim's Algorithm 的主要步驟如下：
- 初始化
d[0]為 0，其他頂點的d[i]為無限大。 - 迴圈 N 次，每次找到不在 MST 中且
d[i]最小的頂點a。 - 將頂點
a加入 MST，並更新與a相鄰的頂點的d[i]值。 - 迴圈結束後，
d[i]儲存了 MST 中每個頂點到 MST 的最小距離，將這些距離加總即可得到 MST 的總權重。
複雜度分析
- 時間複雜度: O(N^2)，其中 N 是頂點的數量。這是因為在每次迭代中，我們需要遍歷所有頂點來找到最小距離的頂點。
- 空間複雜度: O(N^2)，主要用於儲存鄰接矩陣
adj。
程式碼
#include <iostream>
using namespace std;
int n,m,ans,x,y,v,adj[101][101]; // adjacency matrix
int d[101]; // 記錄目前的MST到圖上各點的距離
bool visit[101]; // 記錄各個點是不是已在MST之中
void prim(){
for (int i=0; i<n; i++) d[i] = 1e9;
// 選擇任意一點做為樹根。此處選擇第零點做為樹根。
d[0] = 0;
for (int i=0; i<n; i++){
// 找不在樹上、離樹最近的點。
int a = -1, b = -1, min = 1e9;
for (int j=0; j<n; j++)
if (!visit[j] && d[j] < min){
a = j; // 持續記錄最近的點
min = d[j];
}
// 從起點可連通的點已經找完
if (a == -1) break;
visit[a] = 1;
// relaxation
// 此處與Dijkstra's Algorithm不同，離樹最近，不是離根最近。
for (b=0; b<n; b++)
if (!visit[b] && adj[a][b] < d[b])
d[b] = adj[a][b];
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
if(i==j)
adj[i][j]=0;
else
adj[i][j]=1e9;
}
for(int i=0;i<m;++i){
cin >> x >> y >> v;
adj[x][y]=min(adj[x][y],v);
adj[y][x]=min(adj[y][x],v);
}
prim();
for(int i=0;i<n;++i)
ans+=d[i];
cout << ans << "\n";
}