首页 > 编程学习 > 最小生成树(Prim、Kruskal)算法

最小生成树(Prim、Kruskal)算法

发布时间:2022/10/5 15:44:44

目录

一、最小生成树的概念

二、最小生成树的应用

三、Kruskal算法

1、思想

2、步骤

3、代码

四、Prim算法

1、思路

2、步骤

3、代码


一、最小生成树的概念

一个图中可能存在多条相连的边,我们一定可以从一个图中挑出一些边生成一棵树。这仅仅是生成一棵树,还未满足最小,当图中每条边都存在权重时,这时候我们从图中生成一棵树(n - 1 条边)时,生成这棵树的总代价就是每条边的权重相加之和。

红色记号的边我最小生成树的边 

一个有N个点的图,边一定是大于等于N-1条的。图的最小生成树,就是在这些边中选择N-1条出来,连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。 

二、最小生成树的应用

要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树

三、Kruskal算法

上面介绍了最小生成树是什么,现在需要掌握和理解最小生成树如何形成。给你一个图,用一个规则生成一个最小生成树。而在实现最小生成树方面有prim和kruskal算法,这两种算法的策略有所区别,但是时间复杂度一致。

1、思想

Kruskal算法,和并查集关系很大,它的主要思想为:

先构造一个只含 n 个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有 n-1 条边为止。

2、步骤

而算法的具体步骤为:

1、将图中所有边对象(边长、两端点)依次加入集合(优先队列)q1中。初始所有点相互独立。
2、取出集合(优先队列)q1最小边,判断边的两点是否联通。
3、如果联通说明两个点已经有其它边将两点联通了,跳过,如果不连通,则使用union(并查集合并)将两个顶点合并,这条边被使用(可以储存或者计算数值)。
4、重复2,3操作直到集合(优先队列)q1为空。此时被选择的边构成最小生成树。


3、代码

//并查集的简单版本
class MySets
{
public:
	MySets(){}

	MySets(set<Node*> nodes) {
		for (auto cur : nodes) {
			set<Node*> set;
			set.insert(cur);
			setMap.insert(make_pair(cur, set));
		}
	}
	
	//判断是否是同一个集合
	bool isSameSet(Node* from, Node* to) {
		set<Node*> fromSet = setMap[from];
		set<Node*> toSet = setMap[to];
		//判断集合的内存地址是否相同即可
		return fromSet == toSet;
	}
    
	//合并集合
	void Union(Node* from, Node* to) {
		set<Node*> fromSet = setMap[from];
		set<Node*> toSet = setMap[to];
		
		//把to节点全放到from集合中去
		//并且把哈希表中to节点所对应的集合全改为from集合
		for (auto toNode : toSet) {
			fromSet.insert(toNode);
			setMap[toNode] = fromSet;
		}
	}

public:
	unordered_map<Node*, set<Node*>> setMap;
};

class MyCompare
{
public:
	bool operator()(Edge* edge1, Edge* edge2) {
		return edge1->weight < edge2->weight;
	}
};

class Solution
{
public:
	set<Edge*> kruskalMST(Graph graph) {
		set<Node*> s;
		for (auto node : graph.nodes) {
			s.insert(node.second);
		}
		MySets mySets(s);
		priority_queue<Edge*, vector<Edge*>, MyCompare> priorityQueue;
		for (auto edge : graph.edges) {
			priorityQueue.push(edge);
		}
		set<Edge*> result;
		while (priorityQueue.size()) {
			Edge* edge = priorityQueue.top();
			priorityQueue.pop();
			if (!mySets.isSameSet(edge->from, edge->to)) {
				result.insert(edge);
				mySets.Union(edge->from, edge->to);
			}
		}
		return result;
	}
};

四、Prim算法

除了Kruskal算法以外,普里姆算法(Prim算法)也是常用的最小生成树算法。虽然在效率上差不多。但是贪心的方式和Kruskal完全不同。

1、思路

prim算法的核心信仰是:从已知扩散寻找最小。它的实现方式和Dijkstra算法相似但稍微有所区别,Dijkstra是求单源最短路径,而每计算一个点需要对这个点重新更新距离,而prim不用更新距离。直接找已知点的邻边最小加入即可!prim和kruskal算法都是从边入手处理。

2、步骤

对于具体算法具体步骤,大致为:

1、寻找图中任意点,以它为起点,它的所有边V加入集合(优先队列)q1,设置set表setpoint来记录考察过的点,遇到考察过的点的边肯定是不加入队列中的。
2、从集合q1找到距离最小的那个边v1并判断边是否存在未被标记的一点p ,如果p不存在说明已经确定过那么跳过当前边处理,如果未被标(访问)记那么标记该点p,并且与p相连的未知点(未被标记)构成的边加入集合q1, 边v1(可以进行计算距离之类,该边构成最小生成树) 。
3、重复1,2直到q1为空,构成最小生成树 !

3、代码

class MyCompare
{
public:
	bool operator()(Edge* edge1, Edge* edge2) {
		return edge1->weight < edge2->weight;
	}
};

class Solution
{
public:
	set<Edge*> primMST(Graph graph) {
		//解锁的边进入小根堆
		priority_queue<Edge*, vector<Edge*>, MyCompare> priorityQueue;

		//考察过的点放入set中,遇到考察过的点的边肯定是不要的
		set<Node*> pointSet;

		//依次挑选的边放入result里
		set<Edge*> result;
		
		for (auto node : graph.nodes) {  //随便挑一个点作为开始点
			//node.second是开始的点
			if (!pointSet.count(node.second)) {
				pointSet.insert(node.second);
				for (auto edge : node.second->edges) {
					//由一个点解锁相连的所有边
					priorityQueue.push(edge);
				}
				while (priorityQueue.size()) {
					//先弹出解锁边中的最小边
					Edge* priorityQueueTop = priorityQueue.top();
					priorityQueue.pop();
					Node* toNode = priorityQueueTop->to;//可能的新的点
					if (!pointSet.count(toNode)){
						pointSet.insert(toNode);
						result.insert(priorityQueueTop);
						for (auto nextEdge : toNode->edges) {
							//把解锁的新的点的边也放入小根堆
							//会重复放入边,但是不影响最后的结果
							priorityQueue.push(nextEdge);
						}
					}
				}
			}
		}
		return result;
	}
};

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式