最小生成树(Minimum Spanning Tree)

(1)概念

我们知道，树是有$n$个结点，$n-1$条边的无向无环的连通图。

一个连通图的生成树是一个极小的连通子图，它包含图中全部的$n$个顶点，但只有构成一棵树的$n-1$条边。

最小生成树就是一个带权图，每个边都有一个边权，一颗生成树的权值是该树边所有边权的和，$MST$就是所有生成树中最小的一个。

(2)Prim算法（遍历点的算法）

普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在生成树中的顶点（假设为 A 类），剩下的为不在生成树中的（假设为 B 类）。

对于给定的连通网，起始状态全部顶点都归为 B 类。在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。所走过的顶点和边就是该连通图的最小生成树。

int dis[N];
int mp[N][N];
bool vis[N];

void work() {
	int n, m;cin >> n >> m;
	int ans = 0;
    memset(vis, 0, sizeof vis);
    memset(mp, 0x3f3f3f3f, sizeof mp);
    for (int i = 0; i < n; ++i) {
    	int u, v, w;cin >> u >> v >> w;
        mp[u][v] = w;
        mp[v][u] = w;
    }
    for (int i = 0; i < n; ++i) {
        dis[i] = 0x3f3f3f3f;
    }
    dis[0] = 0;
    vis[0] = 1;
    for (int i = 1; i < n; ++i) {
        dis[i] = min(dis[i], mp[0][i]);
    }
    for (int i = 1; i < n; ++i) {
        //这里的外层循环是循环遍数，与i值无关
        double minn = 0x3f3f3f3f;
        int pos = -1;
        for (int j = 1; j < n; ++j) {
            //每次循环找出与已排联通块距离最近的点
            if (!vis[j] && minn > dis[j]) {
                pos = j;
                minn = dis[j];
            }
        }
        ans += minn;
        vis[pos] = 1;
        for (int j = 0; j < n; ++j) {
            //刷新未连接点的距离最小值
            dis[j] = min(dis[j], mp[pos][j]);
        }
    }
    cout << ans << '\n';
}

正确性显然。

复杂度是$O(n^2)$级别的，但是我们可以使用堆优化降到$O(nlogn)$，之后讲最短路的时候会讲堆优化。

(3)Kruskal算法（遍历边的算法）

克鲁斯卡尔算法（Kruskal）是一种使用贪婪方法的最小生成树算法。 该算法初始将图视为森林，图中的每一个顶点视为一棵单独的树。 一棵树只与它的邻接顶点中权值最小且不违反最小生成树属性（不构成环）的树之间建立连边。

利用并查集可以快速实现查找两个点是否已经连接

int n, m;
int f[105];
struct road {
	int a, b, v;
} arr[305];

int find(int a) {
	if (f[a] == a)
		return a;
	else
		return f[a] = find(f[a]);
}

void join(int a, int b) {
	if (find(a) != find(b))
		f[find(a)] = find(b);
}

bool cmp(road a, road b) {
	return a.v < b.v;
}

void work() {
	cin >> n >> m;
	int a, b, c;
	for (int i = 1; i <= n; ++i) {
		f[i] = i;
	}
	int ans = 0;
	for (int i = 0; i < m; ++i) {
		cin >> arr[i].a >> arr[i].b >> arr[i].v;
	}
	sort(arr, arr + m, cmp);
	//先按路的权值排序，如果两点的祖先不是一个就加上然后合并。
	for (int i = 0; i < m; ++i) {
		if (find(arr[i].a) != find(arr[i].b)) {
			ans += arr[i].v;
			join(arr[i].a, arr[i].b);
		}
	}
	cout << ans << '\n';
	return 0;
}

正确性证明：

给一带权连通的树一定会有至少一棵生成树，那么这些生成树中间必然会会存在至少一棵最小生成树。

假设$T$是用$kruskal$求出来的最小生成树，而$U$是这个图的最小生成树，要证$U=T$。
然而如果$T\ne U$，那么至少存在一条边在$T$中，不在$U$中，假设存在$k$条边存在$T$中不存在$U$中。
接下来进行$k$次变换：
每次将在$T$中不在$U$中的最小的边$f$拿出来放到$U$中，那么$U$中必然形成一条唯一的环路，我们取出这个环路上最小的且不在$T$中的边$e$放回到$T$中，这样的边$e$一定是存在的，因为之前的$T$不存在环路（如果$e$在$T$中那么就可能和$f$形成环路）。

现在证明$f$和$e$权值的关系：

假设$f<e$,那么后来形成的$U$是权值之和更小了，与$U$是最小生成树矛盾。 实际上，不可能在$U$中拿到大于$f$的边，因为把$f$拿走后，如果小于$f$的边都不成立，至少$f$是一个符合条件的边会被那回。

假设$f>e$,那么根据$kruskal$的做法，$e$是在$f$之前被取出来的边但是被舍弃了，一定是因为$e$和比$e$小的边形成了环路，而比$e$小的边都是存在$U$中的，而$e$和这些边并没有形成环路，于假设矛盾。

于是$f$一定和$e$相等的，$k$次变换后，$T$和$U$的权值之和是相等的。

最小生成树的值也是相等的。

复杂度是$O(nlogn)$级别的，一般有mst就用这个。

int f[N];
struct road {
    int a, b, v;
} arr[N];
int tot = 0;

int find(int a) {
    if (f[a] == a)  return a;
    return f[a] = find(f[a]);
}

void join(int a, int b) {
    if (find(a) != find(b)) f[find(a)] = find(b);
}

bool cmp(road a, road b) {
    return a.v < b.v;
}

void work() {
    int a, b;cin >> a >> b;
    for (int i = 1; i <= b; ++i) {
        f[i] = i;
        arr[i] = {0, i, a};
    }
    tot = b;
    for (int i = 1; i <= b; ++i) {
        for (int j = 1; j <= b; ++j) {
            int x; cin >> x;
            if (x == 0) continue;
            else arr[++tot] = {i, j, x};
        }
    }
    ll ans = 0;
    sort(arr + 1, arr + 1 + tot, cmp);
    for (int i = 1; i <= tot; ++i) {
        if (find(arr[i].a) != find(arr[i].b)) {
            ans += arr[i].v;
            join(arr[i].a, arr[i].b);
            b--;
        }
        if (b == 0) break;
    }
    cout << ans << '\n';
}