图论——最小生成树

图论——最小生成树

A wise man changes his mind, a fool never will

生成树

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

最小生成树

在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。

Prim算法(一般用于稠密图——邻接矩阵)

思想(贪心)

每次将离连通部分的最近的点和点对应的边加入的连通部分，连通部分逐渐扩大，最后将整个图连通起来，并且边长之和最小。

代码

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w,表示点 u 和点 v 之间存在一条权值为 w的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 505, INF = 0x3f3f3f3f;

int g[N][N], dist[N];
int n;
bool st[N];

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
	
    for (int i = 0; i < n; i ++) {
        int t = -1;
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        st[t] = true;
        if (i)  res += dist[t];

        for (int j = 1; j <= n; j ++)   dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    int m;
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m --) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if (t == INF)   cout << "impossible" << endl;
    else    cout << t << endl;
    return 0;
}

Kruskal 算法(一般用于稀疏图——邻接表)

思想

• 将所有边按照权值的大小进行升序排序，然后从小到大一一判断。
• 如果这个边与之前选择的所有边不会组成回路(并查集)，就选择这条边；反之，舍去。
• 直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。
• 筛选出来的边和所有的顶点构成此连通网的最小生成树。

代码

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u和点 v 之间存在一条权值为 w的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围

$1<=n<=10^5$

$1<=m<=2?10^5$

图中涉及边的边权的绝对值均不超过 1000。

输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

struct node {
	int a, b, w;
	
	bool operator< (node &b)const {
		return w < b.w;
	}
}e[N * 2];

int p[N];

int find(int x) {
	if (p[x] != x)
		p[x] = find(p[x]);
	return p[x];
}

int n, m;

int kruskal() {
	sort(e, e + m);
	
	for (int i = 1; i <= n; i ++)	p[i] = i;
	
	int res = 0, cnt = 0;
	for (int i = 0; i < m; i ++) {
		int a = e[i].a, b = e[i].b, w = e[i].w;
		a = find(a), b = find(b);
		if (a != find(b))
		{
			p[a] = p[b];
			++ cnt;
			res += w;
		}
	}
	if (cnt < n - 1)	return INF;
	return res;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i ++) {
		int a, b, w;
		cin >> a >> b >> w;
		e[i] = {a, b, w};
	}
	
	int t = kruskal();
	
	if (t == INF)	cout << "impossible" << endl;
	else	cout << t << endl;
	
	return 0;
}