生成树是指无向图中连通且n个顶点n - 1条边的树。最小生成树就是构造连通图的最小代价的生成树。
最小瓶颈树就是在树上最大的边权值在所有生成树中最小。那么有一个定理,最小生成树就是最小瓶颈树,但最小瓶颈树不一定是最小生成树。
解决最小生成树有两种算法分别为:Prim(不常用)和Kruskal(常用)
两种算法分别需要不同的数据结构,分别为Prim(小根堆)和Kruskal(并查集)
两种算法的角度不同:Prim是从顶点考虑边,而Kruskal是从边考虑顶点
当然两种算法的本质是:贪心策略
但Kruskal是不需要建图的就可以求出最小权值,而Prim算法需要建图
但Prim算法可以优化成在点比边少的情况下,比Kruskal快
Kruskal算法实现(借助并查集,从边的角度建树)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 100001//最大集合个数
typedef struct {
int f;
int t;
int w;
}ELEMENT;
void quickSort(ELEMENT *a, int low, int high);//快排的接口
void swap(ELEMENT *a, int low, int high);//交换a[low]和a[high]的值
int* partition(ELEMENT *a, int low, int high, ELEMENT key);//把a中low到high的数按照key分类,小于key的在左边,等于key的在中间,大于key的在右边
ELEMENT edge[2 * N + 1];//存放边的数组,因为边最多有2 * 10 ^ 5题目给出的
int n;//集合的个数
int m;//操作的次数
int f[N];//f[i]表示元素i的下一个元素是谁,如果f[i]等于i那么f[i]就是整个集合的代表元素
//查询元素x在那个集合里面
int find(int x) {
if (x != f[x]) {//只要不是集合的代表元素
f[x] = find(f[x]);//路径压缩
}
return f[x];//返回集合的代表元素,向下传递的过程
}
//判断元素a和b是不是在同一个集合当中
bool isSameSet(int a, int b) {
return find(a) == find(b);//判断代表两个集合的代表元素相同不相同就可以了
}
//合并两个集合
void unionSet(int a, int b) {
f[find(a)] = find(b);//直接左边的合并到右边,对应着指向根节点
}
int main(int argc, char* argv[])
{
sc("%d %d", &n, &m);
//初始化集合
for (int i = 1; i <= n; i++) {
f[i] = i;
}
for (int i = 0; i < m; i++) {//读入边和对应的权重
sc("%d%d%d", &edge[i].f, &edge[i].t, &edge[i].w);
}
quickSort(edge, 0, m - 1);//随机快速排序从小到大按照边的权重排序
int cnt = 0;//统计选取边的数量
int ans = 0;//每条边的权重和即答案
for (int i = 0; i < m && cnt < n - 1; i++) {//遍历完整个边的数组或者选取边的数量已经成了最小生成树了,那么跳出循环,不用再遍历了
if (!isSameSet(edge[i].f, find(edge[i].t))) {//如果选取的边不会和之前选取的边构成环,那么就可以选取这条边
ans += edge[i].w;//选取了这条边,所以加上对应的权重
cnt++;//选取边的数量加一
unionSet(edge[i].f, edge[i].t);//放入选取边的集合
}
}
if (cnt == n - 1) {//如果选取的边的个数等于n - 1条,代表有最小生成树,输出权重和
pr("%d", ans);
}
else {//没有最小生成树,输出orz
pr("orz");
}
return 0;
}
void quickSort(ELEMENT *a, int low, int high)
{
int *p = NULL;//存储等于基准值的左右边界
if ( low >= high) {//如果只有一个值不用排序就直接结束排序
return ;
}
p = partition(a, low, high, a[low + rand() % (high - low + 1)]);//p指向等于基准值区间左右边界
quickSort(a, low, p[0] - 1);//只排小于基准值的部分
quickSort(a, p[1] + 1, high);//只排大于基准值的部分
free(p);//释放掉开辟的空间
}
void swap(ELEMENT *a, int low, int high)
{
ELEMENT t = {0};
t = a[low];
a[low] = a[high];
a[high] = t;
}
int* partition(ELEMENT *a, int low, int high, ELEMENT key)
{
int l = low;//代表等于key区间的左边界,或者是小于区间的下一个数
int r = high;//代表等于key区间的右边界,或者是大于区间的下一个数
int i = low;//从头开始遍历
while(i <= r) {//只要没有到大于区间
if (a[i].w < key.w) {//下标i的数小于基准值,放在左边界里面
swap(a, l++, i++);//把左边界的后一个数和下标i的值交换,然后左区间扩张,然后去看下一个数
}
else if (a[i].w > key.w){//下标i的数大于基准值,放在右边界里面
swap(a, r--, i);//把右边界的前一个数和下标i的值做交换,然后右区间扩张,但i不能动,因为当前i的值还没有访问过
}
else {//下标i的数等于基准值,放在左右边界之间
i++;//直接加1
}
}
int *p = (int *)malloc(sizeof(int ) * 2);//存放等于区间的左右边界
p[0] = l;//等于区间左边界就是l
p[1] = r;//等于区间左边界就是r
return p;//返回等于key区间的左右边界
}
时间复杂度是O(m * logm) + O(n) + O(m),m是边的数量,n是节点的数量。
标签:int,最小,生成,high,low,key,ELEMENT From: https://www.cnblogs.com/lwj1239/p/17982040