【贪心】Prim和Kruskal算法的区别

Kruskal算法和Prim算法的优劣

Kruskal算法，相较于Prim算法是基于点的操作，Kruskal算法是基于边的操作，思想也比Prim简单，更容易理解

Prim算法是采用从点方面考虑来构建MST的一种算法，Prim 算法在稠密图中比Kruskal优。

示例

Prim算法

1. 从源点出发，把源点所有的边加入一个集合（称为待选边集合E{}） 图1
2. 从E{}中选出最短边，连接并移除，并将该点的所有的边加入E{}       图2
3. 不断重复此步骤，如果遇到边已连接，则跳过此边并从E{}移除。

步骤图

1.

2.

3.

4.

5.

6.

7.

Kruskal算法

与Prim算法不同的是，

1. 先将所有的边排序
2. 连接并移除当前最短边，不断重复
3. 如果步骤2遇到边的连接会形成环形，则跳过此边并移除。 如图5

步骤图

1.

2.

3.

4.

5.

6.

7.

Prim算法与Kruskal算法都是用来求连通网的最小生成树问题的方法。首先让我们来创设一个情景：

• 某营业厅接到一个单子，要求给一所学校新建校区安装宽带
• 该学校教学楼、宿舍分别用(A， B， C， D， E， F， G)来代表
• 问：如何修路保证各个站点都能连通，并且线路最短
  

Prim算法

1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
	a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
	b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。

以上是来自百度百科对Prim的描述，那他到底是怎么执行的呢，我们看看流程图

• 首先我们确定一根节点，然后从此节点出发，利用贪心算法寻找权值最小的边。逐步扩大所含顶点的数目，直到遍及连通图的所有顶点。

• 这里我们选取A点为起始点，那么Prim的流程就如下图所示

• 最后黄色所连成的树就是Prim算法的最小生成树

Kruskal算法

百度百科中对Kruskal是这样描述的：

克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树

• 其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止
• 流程如下

Prim算法与Kruskal算法比较

Prim算法的核心步骤是增加点，针对点考察边，与网中的边数无关，因此适合求解稠密图最小生成树。Kruskal算法是针对一条边的扫描和排序，借助“堆”存放。

Prim算法实现

pass

Kruskal算法实现

pass

最小生成树实现

约定

只考虑连通图。

边的权重可以为负数或者是0。

原理

用一条边连接树中的任意的两个顶点都会产生一个新的环。

从树中删去一条边会得到两个独立的树。

切分：图的一种切分是将图中所有的顶点分为两个非空且不重叠的两个集合。

横切：便是一条连接两个属于不同集合的顶点的边。

切分定理：在一幅加权图中，给定任意的切分，它的横切边中的最小权重者必然属于图中的最小生成树。

在假设所有的边的权重均不相同的情况下，每一幅连通图都只有一颗唯一的最小生成树。

切分定理表明对于每一种的切分，权重最小的横切边必然属于最小生成树。

贪心：切分定理是解决最小生成树的基础。

Prim算法

在这里只需要存边，不管结点的事。或许换句话说，就是现在边才是“上司”，谁还管小职员呢
主要是通过三步筛选得到一个关于选择的最小生成树的边集add_e。

#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int u;
	int v;   //与该边相连的两个结点
	double w;//该边的权值
	
	bool operator<(const Edge&a)const{
		return w>a.w;
	}
};

int node, edge;
int vis[100000] = {0}; //结点数组,查看是否走过
//三步筛选
vector<Edge>all_e;//存全部的边
priority_queue<Edge>vis_e;//这个是最小生成树的"candidates"
queue<Edge>add_e;//对于已经加入最小生成树中的边是不动的

void Visit() {
	cout << "共有多少结点?";
	cin >> node;
	cout << endl << "共有多少边？";
	cin >> edge;

	for (int i = 0; i < edge; i++) {
		Edge a;
		//输入格式为：起点-终点-权值
		cin >> a.u >> a.v >> a.w;
		all_e.push_back(a);
	}
}

void add(int start) { //把与该结点有关的边全部加入优先队列
	vis[start] = 1;
	for (int i = 0; i < all_e.size(); i++) {
		if (all_e[i].u == start || all_e[i].v == start)vis_e.push(all_e[i]);
	}
}

void Prim(int start) { //起始节点
	add(start);
	while (!vis_e.empty()) {
		Edge a = vis_e.top();
		vis_e.pop();
		if (vis[a.u] && vis[a.v])continue;//说明会构成环
		else add_e.push(a);//不然就加入最小生成树
		if (!vis[a.u]) add(a.u);//把另外一个结点相连的所有边加入候选人
		if (!vis[a.v]) add(a.v);
	}
}

void Show() { //已经得到了最小生成树的所有边，输出
	while (!add_e.empty()) {
		Edge a = add_e.front();
		add_e.pop();
		cout << a.u << " " << a.v << " " << a.w << endl;
	}
}

int main() {
	int s;
	Visit();//获得所有存在的边
	cout << "选定开始的起点：";
	cin >> s;
	Prim(s);
	Show();
	return 0;
}

过的洛谷板子题P3366

上述的并不能直接套到这个题里面，然后还T了8 9 10三个点。
需要进行一些优化。
显然，需要进行一个大修的操作。【已经修改完毕】
结论：基本上是和原来的代码完全不同了。使用了链式前向星+堆优化。（是一个类似Dijkstra算法算最短路径的操作）

#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647; //2^31-1
const int MAXN = 6000006;

struct Edge {
	int to;//终点
	int w;//权值
	int next;//实际上是上一点
};

struct Node {
	int node;//编号
	int cost;

	bool operator<(const Node &a)const {
		return cost > a.cost;
	}
};

int node, edge, cnt = 1;
int vis[100000] = {0}; //结点数组
Edge edgeTo[MAXN];//与父节点
int head[MAXN];
int dis[MAXN];//得到父节点到其他点的最短路径

void init() {
	for (int i = 0; i < node; i++)head[i] = -1;
}

void add(int from, int to, int w) {
	edgeTo[cnt].to = to;
	edgeTo[cnt].w = w;
	edgeTo[cnt].next = head[from]; //起始：next=-1;类似头插法，指针操作
	head[from] = cnt++; //起点的第一条边指向cnt
}

void Visit() {
	int u, v, w;
	init();
	cin >> node >> edge;

	for (int i = 0; i < edge; i++) {
		//输入格式为：起点-终点-权值
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}
}

int Prim(int start) { //起始节点
	for (int i = 1; i <= node; i++)dis[i] = INF;//初始化
	dis[start] = 0;
	int cnt_node = 0, sum = 0;

	priority_queue<Node>q;
	q.push(Node{start, 0});
	while (!q.empty()) {
		int u = q.top().node;
		q.pop();
		if (!vis[u]) {
			vis[u] = 1;
			cnt_node++;
			sum += dis[u];
			dis[u] = 0; //并入集合内部，因此dis=0
			for (int i = head[u]; i; i = edgeTo[i].next) {
				int &t = edgeTo[i].to;
				if (!vis[t] && dis[t] > dis[u] + edgeTo[i].w) {
					dis[t] = dis[u] + edgeTo[i].w;
					q.push(Node{t, dis[t]});
				}
			}
		}
	}
	if (cnt_node < node)sum = -1;
	return sum;
}

int main() {
	int s, sum = 0;
	Visit();//获得所有存在的边
	int n = Prim(1);
	if (n == -1)cout << "orz";
	else cout << n;
	return 0;
}

Kruskal算法

需要使用一个并查集的操作。
并查集的数据结构如下：

#include <iostream>
using namespace std;
const int maxn = 1e5;
int father[maxn];

void Init() {
	for (int i = 1; i < maxn; i++) father[i] = i
}

void Union(const int &u, const int &v) { //联合
	father[Find(u)] = Find(v); //v的最老祖宗的爹是u的最老祖宗的爹
}

int Find(const int &u) { //查找u的祖宗是谁
	if (u == father[u])return u;
	return father[u] = Find(father[u]); //扁平化
}

int main() {
	Init();
	return 0;
}

【Kruskal】

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct Edge {
	int u;//起点
	int v;//终点
	int w;//权值

	bool operator<(const Edge &a)const {
		return w > a.w;
	}
};

int node, edge; //总结点数以及边数
priority_queue<Edge> all_e;//存放所有的边
queue<Edge> vis_e;//加入最小生成树的所有的边
const int maxn = 1e5;
int father[maxn];

void Init() {
	for (int i = 1; i < maxn; i++) father[i] = i;
}

int Find(const int &u) { //查找u的祖宗是谁
	if (u == father[u])return u;
	return father[u] = Find(father[u]); //扁平化
}

void Union(const int &u, const int &v) { //联合
	father[Find(u)] = Find(v); //v的最老祖宗的爹是u的最老祖宗的爹
}

void Visit() {
	cout << "【请输入结点数以及边数】:" << endl;
	cin >> node >> edge;
	cout << "【请按照 起点-终点-权值 的格式输入边】：" << endl;
	for (int i = 0; i < edge; i++) {
		Edge a;
		cin >> a.u >> a.v >> a.w;
		all_e.push(a);
	}
}

int Kruskal() {
	int n_edge = 0, sum = 0;
	while (!all_e.empty()) {
		Edge a = all_e.top();
		all_e.pop();
		if (Find(a.u) != Find(a.v)) { //就加入这条边
			Union(a.u, a.v);
			vis_e.push(a);
			sum += a.w;
			n_edge++;
		}
	}
	if (n_edge < node - 1)sum = -1;
	return sum;
}

void Show() {
	while (!vis_e.empty()) {
		Edge a = vis_e.front();
		vis_e.pop();
		cout << a.u << " " << a.v << " " << a.w << endl;
	}
}

int main() {
	Init();
	Visit();
	cout << "===========" << endl;
	int n=Kruskal();
	if(n==-1)cout<<"此图不连通"<<endl;
	else {
		cout<<n<<endl;
		Show();
	}
	return 0;
}

这个稍作修改就可以ACP3366了。。。