算法——最小生成树

Prim算法：

算法步骤：
1.选择一个起始节点作为最小生成树的起点。
2.将该起始节点加入最小生成树集合，并将其标记为已访问。
3.在所有与最小生成树集合相邻的边中，选择权重最小的边和它连接的未访问节点。
4.将该边和节点加入最小生成树集合，并将该节点标记为已访问。
重复步骤3和步骤4，直到最小生成树集合包含了图中的所有节点。

#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;int n;
int wei[101][101];
bool visit[101];int prim()
{int res = 0;//总共加n-1条边for (int k = 0; k < n - 1; k++){int mi = 999999;int idex;//先把节点1加入，所以是从2开始遍历for (int i = 2; i <= n; i++){if (visit[i] == 1){continue;}//找到当前已经加入的集合到其余节点的最小边的距离if (mi > wei[1][i]){mi = wei[1][i];idex = i;}}visit[idex] = 1;res += wei[1][idex];for (int i = 2; i <= n; i++){//更新当前已经加入的集合到其余节点的最小边的距离，统一以1为标记点。//新加入的为index，所以对index往外的每条边都要判断是否需要更新if (wei[idex][i] < wei[1][i]){wei[1][i] = wei[idex][i];}}}return res;
}int main()
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){cin >> wei[i][j];}}cout << prim();
}

堆优化Prim算法：

算法步骤
初始化dist 数组为INF，表示所有节点到集合的距离为无穷大。
创建一个小根堆,堆中的元素为(dist 值, 节点编号)。
堆中先插入 ( 0 , 1 )  表示节点1进入集合， dist 值为 0。
每次从堆中取出 dist 值最小的元素 (d,u)，将u加入集合。
对 u 相邻的所有节点 v，更新 dist[v]=min(dist[v],g[u][v])，并更新堆中的相应元素。
重复步骤 4、5，直到所有节点都加入集合。
最后根据取出的 dist 值之和求得最小生成树权重。

#define _CRT_SECURE_NO_WARNINGS#include<iostream>
#include<cstring>
#include<vector>
#include<queue>using namespace std;const int N = 510, M = 1e5 + 10;
typedef pair<int, int> PII;
bool st[N]; // 标记节点是否已经加入最小生成树
int n, m, dist[N]; // dist数组用于记录每个节点到最小生成树的距离
int h[N], e[M], ne[M], idx, w[M]; // 邻接表存储图的边信息void add(int a, int b, int c)
{e[idx] = b; // 存储边的另一个节点w[idx] = c; // 存储边的权值ne[idx] = h[a]; // 将边插入到节点a的邻接表头部h[a] = idx++; // 更新节点a的邻接表头指针
}int Prim()
{int res = 0, cnt = 0; // res用于记录最小生成树的权值和，cnt用于记录已经选择的边数priority_queue<PII, vector<PII>, greater<PII>> heap; // 最小堆，用于选择最短边memset(dist, 0x3f, sizeof dist); // 初始化dist数组为无穷大heap.push({ 0, 1 }); // 将节点1加入最小堆，距离为0dist[1] = 0; // 节点1到最小生成树的距离为0while (heap.size()){auto t = heap.top(); // 取出最小堆中距离最小的节点heap.pop();int ver = t.second, destination = t.first; // ver为节点，destination为距离if (st[ver]) continue; // 如果节点已经在最小生成树中，跳过st[ver] = true; // 将节点标记为已经加入最小生成树res += destination; // 更新最小生成树的权值和cnt++; // 增加已选择的边数// 遍历节点ver的所有邻接边for (int i = h[ver]; i != -1; i = ne[i]){auto u = e[i]; // 邻接边的另一个节点if (dist[u] > w[i]){dist[u] = w[i]; // 更新节点u到最小生成树的距离heap.push({ dist[u], u }); // 将节点u加入最小堆}}}// 如果最小生成树的边数小于n-1，则图不连通，返回0x3f3f3f3f表示不可达if (cnt < n) return 0x3f3f3f3f;return res; // 返回最小生成树的权值和
}int main()
{cin.tie(0);ios::sync_with_stdio(false);memset(h, -1, sizeof h); // 初始化邻接表头指针为-1cin >> n >> m; // 输入节点数和边数for (int i = 0; i < m; ++i){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c); // 添加无向图的边到邻接表中}int t = Prim(); // 计算最小生成树的权值和if (t == 0x3f3f3f3f)cout << "impossible" << endl; // 输出不可达elsecout << t << endl; // 输出最小生成树的权值和return 0;
}

Kruskal算法：

使用结构体存图，结构体中存放点，点，以及这两个点之间边的长度。

首先将结构体排序，按照边的大小从小到大排序。

然后按照边从小到大的顺序依次加入集合。若发现当前边已经在集合中了则跳过。

	// Kruskal 算法求最小生成树 #include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 2e5 + 10; struct node {int x,y,z;}edge[maxn];bool cmp(node a,node b) {return a.z < b.z;}int fa[maxn];int n,m;int u,v,w; long long sum;int get(int x) {return x == fa[x] ? x : fa[x] = get(fa[x]);}int main(void) {scanf("%d%d",&n,&m);for(int i = 1; i <= m; i ++) {scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);}for(int i = 0; i <= n; i ++) {fa[i] = i;}sort(edge + 1,edge + 1 + m,cmp);// 每次加入一条最短的边for(int i = 1; i <= m; i ++) {int x = get(edge[i].x);int y = get(edge[i].y);if(x == y) continue;fa[y] = x;sum += edge[i].z;}int ans = 0;for(int i = 1; i <= n; i ++) {if(i == fa[i]) ans ++;}if(ans > 1) puts("impossible");else printf("%lld\n",sum);return 0;}