首页 > 编程语言 >Kruskal 算法实现最小生成树

Kruskal 算法实现最小生成树

时间：2024-05-27 13:31:08浏览次数：46  
标签：int Kruskal 最小 find 算法 edge rootY rootX 节点

eecf16a5bc2f435990714a3bafaf9f08.png

1.算法思想

将整个图的所有边和权值拿出来，放进一个列表中，再将按权值大小从小到大排列，每次取出权值最小的边放回图中，并在每次放进图的过程中判断放进这个边有没有形成环（形成环的话就不能放进该边），再将当前数的权值相加，求得最小权值。

 

Kruskal算法是一种用于在加权图中找到最小生成树的算法，由Joseph Kruskal在1956年提出。它适用于边权重不一定相等的连通图，包括有向图和无向图。Kruskal算法的基本思想是按照边的权重顺序（从小到大）选择边，确保选择的边不会与已经选择的边形成环，直到选择了足够的边形成最小生成树。

以下是Kruskal算法的基本步骤：

  1. 将图中的所有边按权重从小到大排序。

  2. 初始化一个森林F，其中每个顶点都是一个独立的树。

  3. 按排序后的顺序选择边，对于每条边： a. 如果这条边连接的两个顶点属于F中的不同的树，则将这条边加入到F中，并将两棵树合并为一棵树。 b. 如果这条边连接的两个顶点已经在F中属于同一棵树，则忽略这条边，以避免形成环。

  4. 当F中的树的数量达到1时，算法结束，此时F中的所有边构成了图的最小生成树。

在实际编程中，我们通常需要使用一个并查集数据结构来高效地判断两个顶点是否属于同一棵树，以及合并两棵树。并查集支持两种操作：查找（Find）和联合（Union）。查找操作用于确定一个元素属于哪个集合，而联合操作用于合并两个集合。

2.并查集

并查集是一种数据结构，用于处理一些不交集的合并及查询问题。它支持两种操作：

  1. **find**：确定某个元素属于哪个子集，它可以用来确定两个元素是否属于同一个子集。

  2. **union**：将两个子集合并成一个集合。

在并查集中，每个集合用一棵树来表示，树中的每个节点都保存着一个指向其父节点的引用，根节点的父节点是它自己。

下面是您提供的并查集类的解释：

  • parent：一个向量，用于存储每个元素的父节点。初始时，每个元素的父节点都是它自己，这意味着每个元素都是一个单独的集合。

  • rank：一个向量，用于存储每个集合的秩（树的高度）。在路径压缩的过程中，我们不需要精确的树高度，只需要知道相对大小关系，因此秩是一个足够的信息。秩较小的树总是作为子树连接到秩较大的树上。

构造函数 DisjointSet(int n) 初始化一个有 n 个元素的并查集。它将 parent 向量初始化为每个元素指向自己的状态，并将 rank 向量初始化为 0。

find(int x) 方法用于查找元素 x 所在集合的代表元素（根节点）。如果 x 的父节点不是 x 本身，说明 x 不是根节点，递归地查找其父节点的根节点，并进行路径压缩，即将 x 直接连接到其根节点上，这样可以加快后续查找操作的速度。

1. find() 查找父节点 （路径压缩）

890b129ef1a24f37b7b71f6d959765ad.png

路径压缩是并查集中的一个优化技巧，它的目的是在执行 find 操作时减少树的高度，从而加快后续的 find 操作。路径压缩是在查询过程中实时进行的，不需要额外的数据结构或预处理。

为什么需要路径压缩？

  1. 减少查找时间：在未优化的并查集中，find 操作可能需要遍历从查询节点到根节点的整条路径。如果树的高度很大，这会导致 find 操作的时间复杂度变高。路径压缩可以将这个路径上的所有节点直接连接到根节点，从而将未来的查找时间减少到几乎恒定的时间复杂度。

  2. 保持树的平衡：虽然路径压缩不直接针对树的平衡，但它可以间接地帮助维持树的结构更加平衡。通过压缩路径，我们可以避免在某些操作（如 union）后树变得过高，这有助于保持整体操作的效率。

  3. 提高整体算法效率：在许多算法中，如Kruskal算法用于查找最小生成树，频繁的 find 操作是必要的。路径压缩可以显著减少这些操作的时间，从而提高整个算法的效率。

路径压缩是如何工作的？

路径压缩发生在 find 操作中。当 find 操作被调用时，它在返回根节点之前，会将查询节点及其所有祖先节点的父节点设置为根节点。这样，原本可能很长的路径被压缩成了一条从查询节点直接到根节点的边。

//查询父节点
int find(int x) {
	if (parent[x] != x) {
		//路径压缩
		parent[x] = find(parent[x]);
	}
	return parent[x];
}

unionSet(int x, int y) 方法用于合并元素 x 和 y 所在的集合。首先找到 x 和 y 的根节点 rootX 和 rootY。如果它们不相等，说明 x 和 y 不在同一个集合中，需要合并。为了保持树的平衡，我们总是将秩较小的树连接到秩较大的树上。如果两棵树的秩相同，我们将任意一棵树作为子树连接到另一棵树上，并增加后者树的秩。

并查集是Kruskal算法实现的关键部分，用于快速判断图中两个顶点是否属于同一个连通分量，从而避免在最小生成树中形成环。

2. unionSet 合并两个不相交的子集 （按秩合并）

在并查集中，unionSet 方法的作用是合并两个不相交的集合。当我们将两个元素 x 和 y 合并时，我们希望它们属于同一个集合，这意味着它们将共享同一个根节点。（判断树是否围成环）

这里是 unionSet 方法的详细步骤：

  1. 首先，我们使用 find 方法找到 x 和 y 的根节点，分别存储在 rootX 和 rootY 中。根节点是那些其父节点指向自己的节点。

  2. 如果 rootX 和 rootY 相同，说明 x 和 y 已经在同一个集合中，不需要进行任何操作。

  3. 如果 rootX 和 rootY 不同，我们需要合并这两个集合。为了保持树的平衡，我们总是将秩较小的树作为子树连接到秩较大的树上。这是因为树的秩可以被视为树的大小的估计，而我们将较小的树连接到较大的树上可以最小化树的高度。

  4. 如果两棵树的秩相同，我们可以任意选择一棵树作为子树，这里我们选择 rootX 作为子树。我们将 rootX 的父节点设置为 rootY，这样 rootX 所在的树就成为了 rootY 所在树的子树。

  5. 由于我们添加了一个新的层级（将 rootX 作为 rootY 的子节点），我们需要更新 rootY 的秩。如果 rootX 和 rootY 的秩相同，我们将 rootY 的秩增加 1，表示现在这棵树的高度增加了。

通过这种方式，unionSet 方法确保了并查集中的树保持相对平衡，这对于保持 find 操作的高效性至关重要。路径压缩和按秩合并是并查集优化的两个关键技巧，它们使得并查集成为一种非常高效的数据结构，特别适合于处理连通性问题，如Kruskal算法中的最小生成树问题。

//合并元素
void unionSet(int x, int y) {
	//查找x的父节点
	int rootX = find(x);
	//查找y的父节点
	int rootY = find(y);

	//如果rootX != rootY 不同，先判断谁的高度小
	if (rootX != rootY) {
		if (rank[rootX] > rank[rootY]) {
			//确保 rootX 存储的是秩较小的树的根节点，而 rootY 存储的是秩较大的树的根节点。
			swap(rootX, rootY);
		}
		//将轶小的作为子树连接到轶大的点上
		parent[rootX] = rootY;
		if (rank[rootX] = rank[rootY]) {
			//两个父节点的高度相同时，增加 rootY 的秩，表示现在这棵树的高度增加了。
			++rank[rootY];
		}
	}
}

3. Kruskal算法

Kruskal 算法的实现，用于在给定的加权无向图中找到最小生成树（MST）。下面是代码的详细解释：

  1. int n = graph.getAdjacencyList().size(); 获取图的顶点数。

  2. DisjointSet ds(n); 创建一个并查集，用于跟踪连通分量。

  3. vector<Edge> mst; 创建一个向量，用于存储最小生成树的边。

  4. vector<Edge> allEdges; 创建一个向量，用于存储图中的所有边。

接下来，代码进入一个循环，用于收集图中的所有边：

  1. for (int i = 0; i < n; ++i) 遍历图中的每个顶点。

  2. for (const Edge& edge : graph.getAdjacencyList()[i]) 遍历与当前顶点相连的每条边。

  3. allEdges.push_back(edge); 将边添加到 allEdges 向量中。

然后，代码对所有的边进行排序：

  1. sort(allEdges.begin(), allEdges.end(), [](const Edge& a, const Edge& b) { return a.weight < b.weight; }); 使用 lambda 表达式作为比较函数，按边的权重对 allEdges 进行升序排序。

最后，代码进入主循环，用于构建最小生成树：

  1. for (const Edge& edge : allEdges) 遍历排序后的所有边。

  2. if (ds.find(edge.from) != ds.find(edge.to)) 使用并查集的 find 方法检查边的两个顶点是否属于不同的连通分量。

  3. 如果边的两个顶点属于不同的连通分量，执行以下操作：

    • mst.push_back(edge); 将边添加到最小生成树中。

    • ds.unionSet(edge.from, edge.to); 使用并查集的 unionSet 方法将边的两个顶点所在的连通分量合并。

  4. return mst; 返回构建的最小生成树。

整个算法的关键在于按照权重顺序选择边，并使用并查集来避免形成环，从而构建出最小生成树。

//Kruskal算法
vector<Edge>kruskal(AdjacencyList& graph) {
	int n = graph.GetadjacencyList().size();
	DisjoinSet ds(n);     //创建一个并查集，用于跟踪连通分量。
	vector<Edge> mst;     //创建一个向量，用于存储最小生成树的边。
	vector<Edge> allEdges;// 创建一个向量，用于存储图中的所有边。

	//获取所有边
	for (int i = 0; i < n; i++) {
		for (const Edge& edge : graph.GetadjacencyList()[i]) {
			allEdges.push_back(edge);
		}
	}

	//1.按权重大小排序所有边
	sort(allEdges.begin(), allEdges.end(), cmp);

	//2 按权重排序所有边
	/*sort(allEdges.begin(), allEdges.end(), [](const Edge& a, const Edge& b) {
		return a.weight < b.weight;
		});*/

	//遍历所有排序好的边
	for (const Edge& edge : allEdges) {
		//如果当前边不会构成回路，将这两个点放进mst数组中，在将两个点来链接起来
		if (ds.find(edge.from) != ds.find(edge.to)) {
			mst.push_back(edge);
			ds.unionSet(edge.from, edge.to);
		}
	}

	return mst;

}

4.源代码

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

//边结构
struct Edge {
	int from;
	int to;
	int weight;//边权
};

//邻接表类
class AdjacencyList {
private:
	vector<vector<Edge>>adjacencyList;//顺序表
public:
	//初始化操作 构造函数
	AdjacencyList(int num) :adjacencyList(num) {}

	//添加边
	void addEdge(int from, int to, int weight) {
		adjacencyList[from].push_back({ from,to,weight });
		adjacencyList[to].push_back({ to,from,weight });
	}

	//获取顺序表
	vector<vector<Edge>>& GetadjacencyList() {
		return adjacencyList;
	}
};

//并查集类
class DisjoinSet {
private:
	vector<int>parent;//存储每个元素的父节点
	vector<int>rank;//存储每个集合的轶（树的高度）
public:
	//初始化操作 将每个元素的父节点定义为他的本身
	DisjoinSet(int n) :parent(n), rank(n, 0) {
		for (int i = 0; i < n; i++) {
			parent[i] = i;
		}
	}

	//查询父节点
	int find(int x) {
		if (parent[x] != x) {
			//路径压缩
			parent[x] = find(parent[x]);
		}
		return parent[x];
	}

	//合并元素
	void unionSet(int x, int y) {
		//查找x的父节点
		int rootX = find(x);
		//查找y的父节点
		int rootY = find(y);

		//如果rootX != rootY 不同，先判断谁的高度小
		if (rootX != rootY) {
			if (rank[rootX] > rank[rootY]) {
				//确保 rootX 存储的是秩较小的树的根节点，而 rootY 存储的是秩较大的树的根节点。
				swap(rootX, rootY);
			}
			//将轶小的作为子树连接到轶大的点上
			parent[rootX] = rootY;
			if (rank[rootX] = rank[rootY]) {
				//两个父节点的高度相同时，增加 rootY 的秩，表示现在这棵树的高度增加了。
				++rank[rootY];
			}
		}
	}
};
//按权重大小排序所有边
	static bool cmp(const Edge & a, const Edge & b) {
		return a.weight < b.weight;
	}

//Kruskal算法
vector<Edge>kruskal(AdjacencyList& graph) {
	int n = graph.GetadjacencyList().size();
	DisjoinSet ds(n);     //创建一个并查集，用于跟踪连通分量。
	vector<Edge> mst;     //创建一个向量，用于存储最小生成树的边。
	vector<Edge> allEdges;// 创建一个向量，用于存储图中的所有边。

	//获取所有边
	for (int i = 0; i < n; i++) {
		for (const Edge& edge : graph.GetadjacencyList()[i]) {
			allEdges.push_back(edge);
		}
	}

	//1.按权重大小排序所有边
	sort(allEdges.begin(), allEdges.end(), cmp);

	//2 按权重排序所有边
	/*sort(allEdges.begin(), allEdges.end(), [](const Edge& a, const Edge& b) {
		return a.weight < b.weight;
		});*/

	//遍历所有排序好的边
	for (const Edge& edge : allEdges) {
		//如果当前边不会构成回路，将这两个点放进mst数组中，在将两个点来链接起来
		if (ds.find(edge.from) != ds.find(edge.to)) {
			mst.push_back(edge);
			ds.unionSet(edge.from, edge.to);
		}
	}

	return mst;

}
int main() {
	AdjacencyList graph(6);

	// 添加边
	graph.addEdge(0, 1, 4);
	graph.addEdge(0, 2, 3);
	graph.addEdge(1, 2, 1);
	graph.addEdge(1, 3, 2);
	graph.addEdge(2, 3, 4);
	graph.addEdge(2, 4, 2);
	graph.addEdge(3, 4, 2);
	graph.addEdge(3, 5, 1);
	graph.addEdge(4, 5, 6);

	// 执行Kruskal算法
	vector<Edge> mst = kruskal(graph);

	// 打印最小生成树
	cout << "Minimum Spanning Tree:" << endl;
	for (const Edge& edge : mst) {
		cout << "(" << edge.from << ", " << edge.to << ", " << edge.weight << ")" << endl;
	}

	return 0;
}

 

 

标签：int,Kruskal,最小,find,算法,edge,rootY,rootX,节点
From： https://blog.csdn.net/2301_78947898/article/details/139186533

相关文章

  • 高级算法随笔
    高级算法高级算法是C++编程中非常重要的一个方面，它涉及到各种复杂的数据结构和算法设计。比如，常见的高级算法包括动态规划、图论算法、搜索算法等等。在C++中，我们可以利用各种数据结构和STL（StandardTemplateLibrary）来实现这些算法，同时也可以自行设计和优化算法以提高......
  • 01-1.1.2 算法的时间复杂度
    如何评估算法时间开销？存在的问题和机器性能有关和编程语言有关和编译程序产生的机器指令质量有关有些算法不能事后统计运行时间的——>如导弹控制算法算法的时间复杂度——>T=T(n)事前预估算法时间开销T(n)与问题规模n的关系（T表示“time”）算法的时间复杂度用算法表......
  • 57天【代码随想录算法训练营34期】第十章 单调栈part01
    739.每日温度单调栈指的是只增加或只减少的stack，相当于一个memoclassSolution:defdailyTemperatures(self,temperatures:List[int])->List[int]:answer=[0]*len(temperatures)stack=[0]foriinrange(1,len(temperatures)):......
  • 抖音新算法之a_bogus逆向分析
    前言问：抖音的a_bogus值有什么用？1.抖音所有数据的校验都离不开a_bogus。2.抖音作为最大的短视频平台他的数据是十分多且有用的。3.获取批量抖音的数据，例如评论、无水印视频、弹幕监听、直播间抢货等。4.学习使用各种浏览器断点。1.抓包分析我们进入到章若楠的主页面，进......
  • 代码随想录算法训练营第十八天 | 513.找树左下角的值
    513.找树左下角的值题目链接文章讲解视频讲解classSolution{public:intmaxDepth=INT_MIN;intresult;intfindBottomLeftValue(TreeNode*root){intdepth=0;traversal(root,depth);returnresult;}voi......
  • 深入浅出-CAS算法原理
    1、什么是CAS？CAS：CompareandSwap，即比较再交换。jdk5增加了并发包java.util.concurrent.*,其下面的类使用CAS算法实现了区别于synchronouse同步锁的一种乐观锁。JDK5之前Java语言是靠synchronized关键字保证同步的，这是一种独占锁，也是是悲观锁。2、CAS算法理解对CAS的理......
  • day14--Lambda、方法引用、算法、正则表达式、数据结构
    day14–Lambda、方法引用、算法、正则表达式、数据结构一、Arrays类接下来我们学习的类叫做Arrays，其实Arrays并不是重点，但是我们通过Arrays这个类的学习有助于我们理解下一个知识点Lambda的学习。所以我们这里先学习Arrays，再通过Arrays来学习Lamdba这样学习会更丝滑一些_.......
  • 爬山算法介绍
    目录1.概述2.产生3.定义4.优缺点5.应用示例6.未来展望7.示例代码1.概述爬山算法是一种简单的启发式搜索算法，从起始点开始，每次选择当前位置邻域内的最优解作为下一个位置，直到达到目标点或无法继续前进。爬山算法的基本思想是通过逐步逼近最优解来找到最优解。2.产生......
  • 代码随想录算法训练营第三天 |203、707、206
    链表基础理论：https://programmercarl.com/链表理论基础.html203题目链接：https://leetcode.cn/problems/remove-linked-list-elements/203代码随想录：https://programmercarl.com/0203.移除链表元素.html#算法公开课707题目链接：https://leetcode.cn/problems/design-linked-lis......
  • Unity A*寻路算法
    前言：为什么要使用A*寻路算法，不直接使用unity自带的Navigation组件呢？灵活性高：A*算法允许开发者根据具体游戏需求调整和优化算法实现，比如通过改变启发式函数来适应不同的地图和寻路条件。Unity的Navigation组件虽然强大，但在一些特殊场景或需要高度定制的路径计算中可能不够灵......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99