【c++算法篇】--图论之克鲁斯卡尔

下面让我们来具体介绍一下

概念

克鲁斯卡尔是一种求连通图的最小生成树的算法（用最少的路线连接所有点），它的时间复杂度为O（nloge）n为边数

原理

通过以结构体中的权值为排序对象来排序结构体，通过getf（）函数来寻找有没有共同联通点，有的话就跳过，没有的话就进行加边操作并且记录答案，详细内容在下文实现方式中会讲到。 下面让我们用图的形式感受一下： 这里可以发现，1-2最小值为1，所以连接这条线，并且2的“爹”=1； 找完最小的边找第二条边，这时候1和4也就连通了 连接这条边后，他们的爹都统一了，所以就全部连通了

所以现在所有点的爹都有同一个值，那么他们就联通了 在算法中会通过寻找每一个值的爹来判断他们是否连通，如果连通那么就不管，如果没连通，就要进行加边操作，并且记录答案。

作用

通俗易懂的来说，就是用最小的权值连通图中所有点

实现方式

下面来看一道题 P3366 【模板】最小生成树 题目描述 如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式 第一行包含两个整数 N,M表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 X_i,Y_i,Z_i ，表示有一条长度为 Z_i​ 的无向边连接结点 X_i,Y_i 输出格式 如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例 输入 #1复制 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3 输出 #1复制 7 说明/提示 数据规模：

对于 20%20% 的数据，N≤5，M≤20。

对于 40%40% 的数据，N≤50，M≤2500。

对于 70%70% 的数据N≤500，M≤10^4 对于 100%100% 的数据：1≤N≤5000，1≤M≤2×10^5，1≤Z ​≤10 ^4

样例解释： 所以最小生成树的总边权为 2+2+3=72+2+3=7。 这是一道经典的最小生成树模板题，具体细节让我们在代码中体现

#include
#include
#include
#include
#include
using namespace std;
struct node{
	int u,v,w,next;

	bool operator >m;
	for(int i=1;ie[i].u>>e[i].v>>e[i].w;//因为这里是单项图，所以可以直接输入
	}
	int x=kruskal();
	if(x==-1) 
		cout>b>>c;
		add(a,b,c);
	}
	for(i--n){
 		f[i]=i;//初始化，使每个点的爹都是自己
	}
}

例题讲解 例题1

营救 题目背景 “咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

题目描述 妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 t 区，而自己在 s 区。

该市有 m 条大道连接 n 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线，使得经过道路的拥挤度最大值最小。

输入格式 第一行有四个用空格隔开的 n，m，s，t，其含义见【题目描述】。

接下来 m 行，每行三个整数 u, v, w表示有一条大道连接区 u 和区 v，且拥挤度为 w。

两个区之间可能存在多条大道。

输出格式 输出一行一个整数，代表最大的拥挤度。

输入输出样例 输入 #1复制 3 3 1 3 1 2 2 2 3 1 1 3 3 输出 #1复制 2 说明/提示 数据规模与约定 对于 30% 的数据，保证 n≤10。 对于 60% 的数据，保证 n≤100。 对于 100% 的数据，保证 1≤n≤10^4 ,1≤m≤2×10 ^4，w≤10 ^4，1≤s,t≤n。且从 s 出发一定能到达 t 区。 样例输入输出 1 解释 小明的妈妈要从 1 号点去 3 号点，最优路线为 1->2->3。 来看看题解

#include
#include
#include
#include
#include
using namespace std;
int n,m;
	struct edge{
		int u,v,w;
		bool operator n>>m;
	cin>>s>>t;
	for(int i=1;i>a>>b>>c;
		add(a,b,c);
	}
	for(int i=1;i