首页 > 编程语言 >山东大学数据结构与算法实验13最小生成树（Prim算法/Kruskal算法）

山东大学数据结构与算法实验13最小生成树（Prim算法/Kruskal算法）

时间：2024-07-29 09:57:36浏览次数：16  
标签：13 vertexnode weight int next 算法 heap Prim element

A : Prim算法

题目描述

使用 prim 算法实现最小生成树

输入输出格式

输入

第一行两个整数 n,e。n (1≤n≤200000) 代表图中点的个数，e (0≤m≤500000) 代表边的个数。
接下来 e 行，每行代表一条边：

  • i j w 表示顶点 i 和顶点 j 之间有一条权重为 w 的边

输出

最小生成树所有边的权重和

数据结构与算法描述

构造节点结构体包括权、元素大小、下一个节点。

struct vertexnode {
	int weight;
	int element;
	vertexnode* next;
	vertexnode(){}
	vertexnode(const int& element, const int& weight) {
		this->element = element;
		this->weight = weight;
		this->next = NULL;
	}
	
};

在图类中，插入函数与邻接链表类似，终点节点包含了该边的权重，将该节点插入到邻接链表中。因为是无向图，所以反向再来一遍。

class graph {
private:
	int numvertices;//点的个数 
	int numedges;//边的个数 
	vertexnode* list;//邻接链表 
public:
	graph(int n, int e) {
		numvertices = n;
		numedges = e;
		list = new vertexnode[n + 1];
		for (int i = 1; i <= n; i++) {
			list[i].element = i;
			list[i].next = NULL;
			list[i].weight = 0;
		}
	}
	void insert(int i, int j, int w);
	void prim();
};
void graph::insert(int i, int j, int w) {
	vertexnode* insertnode = new vertexnode(j,w);//创造一个终点的节点 
	vertexnode* nextnode = list[i].next;//与起点相连的点 
	if (nextnode == NULL) {//没有相连的点，直接连 
		list[i].next = insertnode;
	}
	else {
		list[i].next = insertnode; 
		insertnode->next = nextnode;
	}
	vertexnode* insertnode1 = new vertexnode(i, w);//因为是无向图，所以反向再来一遍 
	vertexnode* nextnode1 = list[j].next;
	if (nextnode1 == NULL) { 
		list[j].next = insertnode1;
	}
	else {
		list[j].next = insertnode1; 
		insertnode1->next = nextnode1;
	}
	numedges++;
}

Prim函数，利用最小堆，从1点开始循环，循环次数为定点数减一，将与这个点的邻接点且没有到达过的压入最小堆，将已到达的点从堆中删除，权重和更新，在堆中删除该被加入的节点。最后循环结束输出权重和。

void graph::prim() {
	minHeap mh(numvertices);
	reach[1] = 1;
	vertexnode* nextnode = list[1].next;//第一个点相连的点
	long long sumw = 0;//权重和
	for (int i = 2; i <= numvertices; i++) {//只要numvertices-1次
		while (nextnode != NULL) {//将所有的邻接点压入最小堆
			if (reach[nextnode->element] != 1) {
				vertexnode node(nextnode->element, nextnode->weight);
				mh.push(node);
			}
			nextnode = nextnode->next;
		}
		while (reach[mh.top().element] == 1) {//已经到达的点删除
			mh.pop();
		}
		sumw += mh.top().weight;
		reach[mh.top().element] = 1;
		nextnode = list[mh.top().element].next;//要把与该点相连的点压入堆
		mh.pop();
	}
	cout << sumw << endl;
}

完整代码（含注释）

#include<iostream>
using namespace std;
struct vertexnode {
	int weight;
	int element;
	vertexnode* next;
	vertexnode(){}
	vertexnode(const int& element, const int& weight) {
		this->element = element;
		this->weight = weight;
		this->next = NULL;
	}
	
};
class minHeap {
private:
	vertexnode* heap;//元素数组
	int heapSize; //堆中的元素个数
	int arrayLength;
public:
	minHeap(int n) {
		heapSize = 0;
		heap = new vertexnode[n + 1];
		arrayLength = n + 1;
	}
	~minHeap() { delete[] heap; }
	bool empty() { return heapSize == 0; }//判断heapSize是否为0.
	int Size() { return heapSize; }//返回heapSize的值
	void push(vertexnode x);
	vertexnode& top() { return heap[1]; }//输出根 
	void pop();
};
void minHeap::push(vertexnode x) {//插入 
	if (heapSize == arrayLength - 1) {//没有足够的空间 
		arrayLength *= 2;
		vertexnode* newheap = new vertexnode[arrayLength];//数组长度加倍 
		for (int i = 1; i <= heapSize; i++) {
			newheap[i] = heap[i];
		}
		delete[] heap;
		heap = newheap;
	}
	int currentNode = ++heapSize;//从新的叶节点开始 
	while (currentNode != 1 && x.weight < heap[currentNode / 2].weight) {//当currentNode没到根节点，并且父节点比插入的大时，继续上升 
		heap[currentNode] = heap[currentNode / 2];//将该元素的父节点下移 
		currentNode /= 2;//移向父节点 
	}
	heap[currentNode] = x;
}
void minHeap::pop() {//删除 
	vertexnode lastElement = heap[heapSize--];//最后一个元素 
	int currentNode = 1;//从当前被删掉的最小元素的位置开始 
	int child = 2;//currentNode的孩子 
	while (child <= heapSize) {
		if (child<heapSize && heap[child].weight>heap[child + 1].weight)child++;//找到左右孩子中更小的 
		if (lastElement.weight <= heap[child].weight)break;//当孩子比要插入的大，则可以插入了，跳出循环 
		heap[currentNode] = heap[child];//将较小的孩子上移 
		currentNode = child;//currentNode向下移 
		child *= 2;
	}
	heap[currentNode] = lastElement;
}
int reach[2000000] = { 0 };
class graph {
private:
	int numvertices;//点的个数 
	int numedges;//边的个数 
	vertexnode* list;//邻接链表 
public:
	graph(int n, int e) {
		numvertices = n;
		numedges = e;
		list = new vertexnode[n + 1];
		for (int i = 1; i <= n; i++) {
			list[i].element = i;
			list[i].next = NULL;
			list[i].weight = 0;
		}
	}
	void insert(int i, int j, int w);
	void prim();
};
void graph::insert(int i, int j, int w) {
	vertexnode* insertnode = new vertexnode(j,w);//创造一个终点的节点 
	vertexnode* nextnode = list[i].next;//与起点相连的点 
	if (nextnode == NULL) {//没有相连的点，直接连 
		list[i].next = insertnode;
	}
	else {
		list[i].next = insertnode; 
		insertnode->next = nextnode;
	}
	vertexnode* insertnode1 = new vertexnode(i, w);//因为是无向图，所以反向再来一遍 
	vertexnode* nextnode1 = list[j].next;
	if (nextnode1 == NULL) { 
		list[j].next = insertnode1;
	}
	else {
		list[j].next = insertnode1; 
		insertnode1->next = nextnode1;
	}
	numedges++;
}
void graph::prim() {
	minHeap mh(numvertices);
	reach[1] = 1;
	vertexnode* nextnode = list[1].next;//第一个点相连的点
	long long sumw = 0;//权重和
	for (int i = 2; i <= numvertices; i++) {//只要numvertices-1次
		while (nextnode != NULL) {//将所有的邻接点压入最小堆
			if (reach[nextnode->element] != 1) {
				vertexnode node(nextnode->element, nextnode->weight);
				mh.push(node);
			}
			nextnode = nextnode->next;
		}
		while (reach[mh.top().element] == 1) {//已经到达的点删除
			mh.pop();
		}
		sumw += mh.top().weight;
		reach[mh.top().element] = 1;
		nextnode = list[mh.top().element].next;//要把与该点相连的点压入堆
		mh.pop();
	}
	cout << sumw << endl;
}
int main() {
	int n, e;
	cin >> n >> e;
	graph g(n, e);
	for (int i = 0; i < e; i++) {
		int y, j, w;
		cin >> y >> j >> w;
		g.insert(y, j, w);
	}
	g.prim();
	return 0;
}

B : Kruskal算法

题目描述

使用 kruskal 算法实现最小生成树

输入输出格式

输入

第一行两个整数 n,e。n (1≤n≤200000) 代表图中点的个数，e (0≤m≤500000) 代表边的个数。
接下来 e 行，每行代表一条边：

  • i j w 表示顶点 i 和顶点 j 之间有一条权重为 w 的边

输出

最小生成树所有边的权重和

数据结构与算法描述

将输入的边的两个顶点和权重插入结构体数组中，将结构体数组压入最小堆，然后进行一个循环，当边数为零或者所加边数等于定点数减一。在循环中，取出堆顶的边，利用并查集，判断该边是否在同一个集合，如果不在则合并，如果在则不能加，避免成环。

	for (int i = 1; i <= e; i++) {//结构体数组 
		cin >> edge[i].vertex1 >> edge[i].vertex2 >> edge[i].weight;
		int t = 0;
	}
	int k = 0;
	long long sumw=0;
	minHeap heap(1);//最小堆 
	heap.initialize(edge, e);
	while (e > 0 && k < n - 1) {
		edgenode x = heap.top();
		heap.pop();
		e--;
		int a = find(x.vertex1);//找该边两个顶点的根 
		int b = find(x.vertex2);
		if (a != b) {//如果不在同一个集合，进行合并 
			unite(a, b);
			k++;
			sumw += x.weight;
		}
	}
	cout << sumw << endl;

并查集find函数：第一个while循环找根，第二个while循环，将所有的点都连到根上，降低高度，节省找根的时间。Unite函数：将两个数合并，两个跟一个为另一个的父节点。

int find(int theelement) {
	int root = theelement;
	while (parent[root] != 0) {//找根 
		root = parent[root];
	}
	while (theelement != root) {//将所有的点都连到根上，降低高度 
		int t = parent[theelement];;
		parent[theelement] = root;
		theelement = t;
	}
	return root;
}
void unite(int a, int b) {//两个树合并 
	parent[b] = a;
}

完整代码（含注释）

#include<iostream>
using namespace std;
struct edgenode {
	long long weight;
	int vertex1;
	int vertex2;
}edge[5000000];
class minHeap {
private:
	edgenode* heap;//元素数组
	int heapSize; //堆中的元素个数
public:
	minHeap(int n) {
		heapSize = 0;
		heap = new edgenode[n + 1];
	}
	~minHeap() { delete[] heap; }
	bool empty() { return heapSize == 0; }//判断heapSize是否为0.
	int Size() { return heapSize; }//返回heapSize的值
	edgenode top() { return heap[1]; }//输出根 
	void pop();
	void initialize(edgenode* theheap, int theSize);
};
void minHeap::pop() {//删除 
	edgenode lastElement = heap[heapSize--];//最后一个元素 
	int currentNode = 1;//从当前被删掉的最小元素的位置开始 
	int child = 2;//currentNode的孩子 
	while (child <= heapSize) {
		if (child<heapSize && heap[child].weight>heap[child + 1].weight)child++;//找到左右孩子中更小的 
		if (lastElement.weight <= heap[child].weight)break;//当孩子比要插入的大，则可以插入了，跳出循环 
		heap[currentNode] = heap[child];//将较小的孩子上移 
		currentNode = child;//currentNode向下移 
		child *= 2;
	}
	heap[currentNode] = lastElement;
}
void minHeap::initialize(edgenode* theHeap, int theSize) {//初始化
	delete[] heap;
	heap = new edgenode[theSize + 1];
	for (int i = 1; i <= theSize; i++) {
		heap[i] = theHeap[i];
	}
	heapSize = theSize;
	for (int root = heapSize / 2; root >= 1; root--) {//从数组中最右一个有孩子的节点开始
		edgenode rootElement = heap[root];//子树的根 
		int child = 2 * root;//rootElement的孩子位置 
		while (child <= heapSize) {
			if (child<heapSize && heap[child].weight>heap[child + 1].weight)child++;//找到孩子里较小的 
			if (rootElement.weight <= heap[child].weight)break;//如果子树的根小于其孩子，则可以跳出循环 
			//如果孩子较小
			heap[child / 2] = heap[child];//将孩子上移 
			child *= 2;
		}
		heap[child / 2] = rootElement;
	}
}
int parent[2000000] = { 0 };
int find(int theelement) {
	int root = theelement;
	while (parent[root] != 0) {//找根 
		root = parent[root];
	}
	while (theelement != root) {//将所有的点都连到根上，降低高度 
		int t = parent[theelement];;
		parent[theelement] = root;
		theelement = t;
	}
	return root;
}
void unite(int a, int b) {//两个树合并 
	parent[b] = a;
}
int main() {
	int n, e;
	cin >> n >> e;
	for (int i = 1; i <= e; i++) {//结构体数组 
		cin >> edge[i].vertex1 >> edge[i].vertex2 >> edge[i].weight;
		int t = 0;
	}
	int k = 0;
	long long sumw=0;
	minHeap heap(1);//最小堆 
	heap.initialize(edge, e);
	while (e > 0 && k < n - 1) {
		edgenode x = heap.top();
		heap.pop();
		e--;
		int a = find(x.vertex1);//找该边两个顶点的根 
		int b = find(x.vertex2);
		if (a != b) {//如果不在同一个集合，进行合并 
			unite(a, b);
			k++;
			sumw += x.weight;
		}
	}
	cout << sumw << endl;
	return 0;
}

如能打赏，不胜感激[叩谢]。

标签：13,vertexnode,weight,int,next,算法,heap,Prim,element
From： https://blog.csdn.net/Water_Star1/article/details/140763027

相关文章

  • 烧录算法制作
    前言在使用Keil的时候，我们一般会通过一个下载器与目标芯片连接，这样就可以实现的代码下载或调试。那么下载器是如何将我们的应用程序烧写在我们芯片内部Flash当中的呢，是否可以同样的方式烧录在外部Flash上呢？这是此片文章所要说明的。MDK下载算法原理通过MDK创建一批与地址信息无......
  • 算法
    算法库函数next_permutation(start,end)prev_permutation(start,end)(全排列函数)[库函数介绍](C++中全排列函数next_permutation用法-CSDN博客)[库函数原理](C++中next_permutation函数的使用方法、原理及手动实现_c++next_permutation-CSDN博客)库函数原理基本解释:......
  • （8-6-05）优先级遍历（Priority-based Search）算法：基于tkinter的多算法路径规划程序（5）
    （7）函数breadth_first_search实现了广度优先搜索算法。它使用一个队列来存储待探索的节点，并通过迭代地从队列中取出节点来搜索路径。在搜索过程中，它会调用`add_neighbours`函数来添加节点的相邻节点，并在添加节点后继续搜索。当找到目标节点时，函数会停止搜索，并调用`paint`函数来......
  • 提高 C# 的生产力：C# 13 更新完全指南
    提高C#的生产力：C#13更新完全指南 前言#预计在2024年11月，C#13将与.NET9一起正式发布。今年的C#更新主要集中在 refstruct 上进行了许多改进，并添加了许多有助于进一步提高生产力的便利功能。本文将介绍预计将在C#13中添加的功能。注意：目前C#13还未......
  • 机器学习算法——常规算法，在同的业务场景也需要使用不同的算法(一)
    ......
  • 408 数据结构线性表算法
    第一章线性表定义：线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。线性表的表示：若用L命名，表示：L=(a1,a2,a3,a4,a5,……,an)线性表的逻辑特性：a1：唯一的表头元素an：唯一的表尾元素除去a1：每个元素有且仅有一个直接前驱除去an：每个元素有且仅有一个直接后继......
  • 深度模型中的优化 - 基本算法篇
    序言在深度学习中，模型优化是提升模型性能与训练效率的关键环节。深度模型通过优化算法不断调整其内部参数，以最小化损失函数，从而实现对复杂数据的有效拟合与预测。本篇章将简要概述深度模型中的几种基本优化算法，包括梯度下降法及其变种，这些算法在推动深度学习领域的发展中起......
  • SciTech-BigDataAIML-Python Time Series Handbook - Kalman filter: 卡尔曼滤波器算
    网上文档:Python时间序列手册:有ipynb和PDF文件:https://filippomb.github.io/python-time-series-handbook/notebooks/07/kalman-filter.htmlMITPDF:AnIntroductiontotheKalmanFilter-MITIllinoisUniversityPDF:UnderstandingtheBasisoftheKalmanF......
  • 408数据结构树算法
    第四章树4.1二叉树的顺序存储#defineMAXSIZE16typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; intsize;}Tree;//初始化二叉树voidinitTree(Tree&T){ for(inti=0;i<MAXSIZE;i++){ T.data[i]=0; //假设0表示空节点 } T.size=0......
  • 408 数据结构图算法
    第五章图5.1图的邻接矩阵存储//无向图的邻接矩阵存储#defineMAXSIZE16 //图的最大顶点个数typedefintVertexType; //顶点类型typedefintEdgeType; //边类型typedefstruct{ VertexTypeVex[MAXSIZE]; //图的顶点集 EdgeTypeEdge[MAXSIZE][MAXSIZE]; //图的边......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99