最小生成樹(Minimum Spanning Tree)

在圖論中，最小生成樹是一個連通圖的生成樹中，所有邊的權值和最小的生成樹。最小生成樹常常用來描述一個帶權無向連通圖的所有節點集合之間的最小連接子樹。

一、最小生成樹的定義

對於一個無向連通圖G=，其中V為節點的集合，E為邊的集合，如果G’=是G的一個生成樹，則E’是E子集，即E’包含E相同點數的邊，並且G’中任意兩點都是聯通的。那麼可以定義一個權重函數w(或者成為邊的權值)，使得w(e)表示圖G中邊e的權重。則可以定義最小生成樹為使得所有被包含在生成樹中的邊權重之和最小的生成樹E’。

二、最小生成樹的算法

1. Prim算法

Prim算法是一種貪心算法。其核心思想是每次加入一個與當前最小生成樹有最短距離的點到生成樹中，直到生成樹覆蓋所有節點。具體實現可以使用優先隊列或者堆優化來加快運行時間。時間複雜度為O(E*logV)或O(V^2)。

#include<iostream>
#include<queue>
using namespace std;
const int MAXN = 1010; 
const int INF = 0x3f3f3f3f;
int mapp[MAXN][MAXN];
int lowcost[MAXN];
bool vis[MAXN];
int n, m;
int Prim() {
    int sum = 0;
    memset(lowcost, INF, sizeof(lowcost));
    memset(vis, false, sizeof(vis));
    lowcost[1] = 0;
    for(int i=1; i<=n; i++) {
        int u = 0;
        for(int j = 1; j lowcost[j])) {
                u = j;
            }
        }
        vis[u] = true;
        sum += lowcost[u];
        for(int v = 1; v mapp[u][v]) {
                lowcost[v] = mapp[u][v];
            }
        }
    }
    return sum;
}
int main() {
    while(cin>>n) {
        memset(mapp, INF, sizeof(mapp));
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j>mapp[i][j];
            }
        }
        cout<<Prim()<<endl;
    } 
    return 0;
}

2. Kruskal算法

Kruskal算法是另一種常見的最小生成樹算法。與Prim算法不同，Kruskal算法是每次加入一條具有最小權重的邊，直到生成樹中包含所有節點。為了避免有環情況，每加入一條邊之前需要判斷其起點和終點是否已經在同一集合中（使用並查集實現）。算法時間複雜度為O(E*logE)或O(E*logV)。

#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge {
    int u, v, w;
}edge[MAXN*MAXN];
int pre[MAXN];
int mapp[MAXN][MAXN];
int n, m;
int Find(int x) {
    if(pre[x] == x) return x;
    return pre[x] = Find(pre[x]);
}
bool Union(int x, int y) {
    int fx = Find(x), fy = Find(y);
    if(fx != fy) {
        pre[fx] = fy;
        return true;
    }
    return false;
}
bool cmp(const Edge& e1, const Edge& e2) {
    return e1.w < e2.w;
}
int Kruskal() {
    for(int i = 1; i<=n; i++) {
        pre[i] = i;
    }
    sort(edge+1, edge+m+1, cmp);
    int ans = 0;
    for(int i = 1; i>n) {
        m = 0;
        memset(mapp, INF, sizeof(mapp));
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j>mapp[i][j];
                if(i<j) {
                    edge[++m].u = i;
                    edge[m].v = j;
                    edge[m].w = mapp[i][j];
                }
            }
        }
        cout<<Kruskal()<<endl;
    }
    return 0;
}

三、最小生成樹的應用

1.公路規劃

在城市規劃中，最小生成樹可以用來找到連接不同地區的最短路徑，以便合理安排公路建設。

2.電纜布線

在電纜布線中，最小生成樹可以用來找到在不同建築物之間連接最短的路徑，以減少花費和切實提高電纜性能。

3.網絡設計

在計算機網絡設計中，最小生成樹可以用來找到連接不同計算機的最短路徑，以便建設網絡的具體拓撲結構。

四、小結

最小生成樹是圖論中常見且重要的問題。Prim和Kruskal算法是兩種解決最小生成樹問題的常見算法，通過不同的加邊方式和數據結構來實現。在真實場景中，最小生成樹應用也很廣泛，例如公路規劃、電纜布線、網絡設計等。讀者在具體應用中，可以深入理解和改進算法，以實現更優秀的性能。