最小生成树(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<=n; j++) {
            if(!vis[j] && (u == 0 || lowcost[u] > lowcost[j])) {
                u = j;
            }
        }
        vis[u] = true;
        sum += lowcost[u];
        for(int v = 1; v<=n; v++) {
            if(!vis[v] && lowcost[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<=n; j++) {
                cin>>mapp[i][j];
            }
        }
        cout<
   <
    
   

#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<=m; i++) {
        if( Union(edge[i].u, edge[i].v)) {
            ans += edge[i].w;
        }
    }
    return ans;
}
int main() {
    while(cin>>n) {
        m = 0;
        memset(mapp, INF, sizeof(mapp));
        for(int i = 1; i<=n; i++) {
            for(int j = 1; j<=n; j++) {
                cin>>mapp[i][j];
                if(i