数据结构-最小生成树

一.最小生成树的定义

从V个顶点的图里生成的一颗树,这颗树有V个顶点是连通的,有V-1条边,并且边的权值和是最小的,而且不能有回路

二.Prim算法

Prim算法又叫加点法,算法比较适合稠密图

每次把边权最小的顶点加入到树中,最小生成树的不是唯一的,但最小边权是唯一的

Prim算法和 Dijkstra

核心代码

/*更新顶点距离树的距离*/
		for(W=0;W<Graph->Nv;W++)/*对图中顶点每个顶点W*/
			if (dist[W] != 0 && Graph->G[V][W] < INFINITY) {
				/*若W是V的邻接点并且未被收录*/
				if (Graph->G[V][W] < dist[W]) {
					/*若收录V使得dist[W]变小*/
					dist[W] = Graph->G[V][W];
					parent[W] = V;/*更新树*/
				}
			}

dist每个顶点的变化

dist[i]=0表示已经加入到最小生成树,距离树的距离是0,65535表示和树没有连接

全部代码

#include<iostream>
using namespace std;

#define INFINITY 65535
#define MaxvertexNum 100
typedef int Vertex;
typedef int WeightType;
Vertex Visited[MaxvertexNum];
Vertex parent[MaxvertexNum];

/*边的定义*/
typedef struct ENode* PtrToENode;
struct ENode
{
	Vertex V1, V2;
	WeightType Weight;/*边权*/
};
typedef PtrToENode Edge;

typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode
{
	Vertex Adjx;/*邻接点下标*/
	WeightType Weight;/*边权*/
	PtrToAdjVNode Next;/*指向下一个邻接点*/
};
typedef struct Vnode {
	PtrToAdjVNode FirstEdge;/*边表头结点*/
	
}AdjList[MaxvertexNum];

/*邻接表*/
typedef struct LGNode* PtrToLGNode;
typedef struct LGNode {
	int Nv;/*顶点数*/
	int Ne;/*边数*/
	AdjList G;
};
typedef PtrToLGNode LGraph;/*邻接表方式存储*/
/*图的定义*/
typedef struct GNode* PtrToGNode;
struct GNode {
	int Nv;/*顶点数*/
	int Ne;/*边数*/
	WeightType G[MaxvertexNum][MaxvertexNum];
};
typedef PtrToGNode MGraph;
LGraph Create(int Vertexnum) {
	Vertex V;
	LGraph Graph = new LGNode();
	Graph->Nv = Vertexnum;
	Graph->Ne = 0;
	for (V = 0; V < Graph->Nv; V++) {
		Graph->G[V].FirstEdge = NULL;
	}
	return Graph;
}
void Insert(LGraph Gaph, Edge E) {
	PtrToAdjVNode NewNode;
	NewNode = new AdjVNode();
	NewNode->Adjx = E->V2;
	NewNode->Next = Gaph->G[E->V1].FirstEdge;
	Gaph->G[E->V1].FirstEdge = NewNode;
	NewNode = new AdjVNode();
	NewNode->Adjx = E->V1;
	NewNode->Next = Gaph->G[E->V2].FirstEdge;
	Gaph->G[E->V2].FirstEdge = NewNode;
}
//插入边
void InsertEdge(MGraph Graph, Edge E) {
	Graph->G[E->V1][E->V2] = E->Weight;
	Graph->G[E->V2][E->V1] = E->Weight;
}
MGraph CreateGraph(int VertexNum) {
	MGraph Graph = new GNode();
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	for (int V = 0; V < Graph->Nv; V++)
		for (int W = 0; W < Graph->Nv; W++)
			Graph->G[V][W] = INFINITY;
	return Graph;
}
MGraph BuildGraph() {
	MGraph Graph;
	Edge E;
	int Nv;/*顶点*/
	cin >> Nv;
	Graph = CreateGraph(Nv);
	cin >> Graph->Ne;
	if (Graph->Ne != 0) {
		for (int i = 0; i < Graph->Ne; i++) {
			E = new ENode();
			cin >> E->V1 >> E->V2 >> E->Weight;
			InsertEdge(Graph, E);
		}
	
	}
	return Graph;

}
Vertex FindMinDist(MGraph Graph, WeightType dist[]) {
	/*返回未被收录顶点中dist最小者*/
	Vertex MinV, V;
	WeightType MinDist = INFINITY;
	for (V = 0; V < Graph->Nv; V++) {
		if (dist[V] != 0 && dist[V] < MinDist) {
			MinDist = dist[V];
			MinV = V;
		}
	}
	if (MinDist < INFINITY)
		return MinV;
	else return 0;
}
int Prim(MGraph Graph, LGraph& MST) {
	/*将最小生成树保存为邻接表存储的图MST,返回最小权重和*/
	/*dist表示顶点到树的距离*/ /*权重*/
	WeightType dist[MaxvertexNum], Tota1Weight;
	
	Vertex V, W;
	int VCount;
	Edge E;
	/*初始化。默认初始点下标是0*/
	for (V = 0; V < Graph->Nv; V++) {
		/*这里假设V到W没有直接边,则Graph->G[V][W]定义INF*/
		dist[V] = Graph->G[0][V];
		parent[V] = 0;/*暂且定义所以顶点的父亲结点都是初始化0*/
	}
	Tota1Weight = 0;/*初始化权重*/
	VCount = 0;/*初始化收入的顶点个数*/
	/*创建一个没有边的邻接表*/
	MST = Create(Graph->Nv);
	E = new ENode();

	/*将初始点0收录MST*/
	dist[0] = 0;
	VCount++;
	parent[0] = -1;/*当前树根是0*/
	while (1) {
		V = FindMinDist(Graph,dist);
		/*V=未被收录顶点中dist最小者*/
		if (V == 0)/*若这样的V不存在*/
			break;/*算法结束*/
		E->V1 = parent[V];/*父亲顶点*/
		E->V2 = V;/*子结点*/
		E->Weight = dist[V];
		Insert(MST, E);
		Tota1Weight += dist[V];
		dist[V] = 0;/*将顶点收录集合树*/
		VCount++;
			
		/*更新顶点距离树的距离*/
		for(W=0;W<Graph->Nv;W++)/*对图中顶点每个顶点W*/
			if (dist[W] != 0 && Graph->G[V][W] < INFINITY) {
				/*若W是V的邻接点并且未被收录*/
				if (Graph->G[V][W] < dist[W]) {
					/*若收录V使得dist[W]变小*/
					dist[W] = Graph->G[V][W];
					parent[W] = V;/*更新树*/
				}
			}
	}/*while结束*/
	if (VCount < Graph->Nv)/* MST中收的顶点不到|V|个*/
		Tota1Weight = 0;
	return Tota1Weight;
}

void DFS(LGraph Graph, Vertex V) {
	cout << V << endl;
	PtrToAdjVNode W;
	Visited[V] = 1;
	for (W = Graph->G[V].FirstEdge; W; W = W->Next) {
		if (Visited[W->Adjx] == 0) {
			DFS(Graph, W->Adjx);
		}
	}
	
}
int main()
{
	MGraph G = BuildGraph();
	LGraph Gr =NULL;
	Prim(G,Gr);
	
	DFS(Gr, 0);
	for (int i = 0; i < G->Nv; i++)
		cout << i<<" " << parent[i] << endl;
	return 0;
}
/*
*
6 10
0 1 6
0 2 1
0 3 5
1 4 3
3 2 4
1 2 5
4 2 6
3 5 2
5 2 4
4 5 6
*/

三.Kruskal算法

Kruskal算法又叫加边法,算法比较适合稀疏图

代码

#include<iostream>
using namespace std;
#define MaxVertexNum 100
typedef int Vertex;
typedef int WeightType;
typedef Vertex ElementType;/*默认元素可以用非负正数表示*/
typedef Vertex SetName;/*默认用根结点的下标作为集合名称*/
typedef ElementType SetType[MaxVertexNum];/*假设集合元素下标从0开始*/
Vertex Visited[MaxVertexNum];
typedef struct ENode* PtrToENode;


struct ENode
{
	Vertex V1, V2;
	WeightType Weight;
};
typedef PtrToENode Edge;

typedef struct AdjVNode* PtrToAdjVNode;

struct AdjVNode
{
	Vertex Adjx;/*邻接点下标 */
	WeightType Weight;/*边权重*/
	PtrToAdjVNode Next;/*向下下一个邻接点*/
};
typedef struct Vnode {
	PtrToAdjVNode FirstEdge;/* 边表头指针*/
	
}AdjList[MaxVertexNum];
typedef struct GNode* PtrToGNode;
typedef struct GNode {
	int Nv;/*顶点个数*/
	int Ne;/*边的个数*/
	AdjList G;
};
typedef PtrToGNode LGraph;/*邻接表方式存储*/

void InsertEdge(LGraph Graph, Edge E);
LGraph CreateGraph(int Vertexnum) {
	Vertex W, V;
	LGraph Graph = new GNode();
	Graph->Nv = Vertexnum;
	Graph->Ne = 0;

	for (V = 0; V < Graph->Nv; V++) {
		Graph->G[V].FirstEdge = NULL;
	}
	return Graph;
}
LGraph BuildGraph() {
	int Nv;
	Vertex V;
	Edge E;
	cin >> Nv;
	LGraph Graph =  CreateGraph(Nv);
	cin >> Graph->Ne;
	if (Graph->Ne != 0) {
		for (V = 0; V < Graph->Ne; V++) {
			E = new ENode();
			cin >> E->V1 >> E->V2 >> E->Weight;
			InsertEdge(Graph, E);
		}
	}
	return Graph;
}
void InsertEdge(LGraph Graph, Edge E) {
	PtrToAdjVNode W;
	W = new AdjVNode();
	W->Adjx = E->V2;
	W->Weight = E->Weight;
	W->Next = Graph->G[E->V1].FirstEdge;
	Graph->G[E->V1].FirstEdge = W;
	W = new AdjVNode();
	W->Adjx = E->V1;
	W->Weight = E->Weight;
	W->Next = Graph->G[E->V2].FirstEdge;
	Graph->G[E->V2].FirstEdge = W;

}
void InitializeVSet(SetType S, int N) {
	/*初始化并查集*/
	ElementType X;
	for (X = 0; X < N; X++)S[X] = -1;
}
void Union(SetType S, SetName Root1, SetName Root2) {
	/*这里默认Root1和Root2是不同集合的根节点*/
	if (S[Root2] < S[Root1]) { /*如果集合2比较大*/
		S[Root2] += S[Root1];/*集合1并入集合2*/
		S[Root1] = Root2;
	}
	else {
		S[Root1] += S[Root2];/*集合2并入集合1*/
		S[Root2] = Root1;
	}
}
SetName Find(SetType S, ElementType X) {
	/*默认集合元素全部初始化为-1*/
	if (S[X] < 0)/*找到集合的根*/
		return X;
	else
		return S[X] = Find(S, S[X]);/*路径压缩*/
}
bool ChekCycle(SetType VSet, Vertex V1, Vertex V2) {
	/*检查连接V1和V2的边是否在现有的最小生成树子集中构成回来*/
	Vertex Root1, Root2;
	Root1 = Find(VSet, V1);/*得到V1所属的连通集名称*/
	Root2 = Find(VSet, V2);/*得到V2所属的连通集名称*/
	if (Root1 == Root2)/*若V1和V2已经连通,则该边不能要*/
		return false;
	else {/*否则改边可以被收集同时将V1和V2并入同一连通集*/
		Union(VSet, Root1, Root2);
		return true;
	}
}

/*边的最小堆*/
/*将N个元素的边数组以ESet[p]为根的子堆调整为关于Weight的最小堆*/
void PerDown(Edge ESet,int p,int N) {
	//直接用数组,不用heap结构了
	int Parent, Child;
	struct ENode X;
	X = ESet[p];
	for (Parent = p; (Parent * 2 + 1) < N; Parent = Child) {
		Child = Parent * 2 + 1;
		if ((Child != N - 1) && (ESet[Child].Weight > ESet[Child + 1].Weight))
			Child++;
		if (X.Weight <= ESet[Child].Weight)
			break;
		else/*下滤*/
			ESet[Parent] = ESet[Child];
	}
	ESet[Parent] = X;
}
/*将图的边存入数组ESet,并且初始化为最下堆*/
void InitializeESet(LGraph Graph, Edge ESet) {
	Vertex V;
	PtrToAdjVNode W;
	int ECount;

	/*将图的边存入数组ESet*/
	ECount = 0;
	for(V=0;V<Graph->Nv;V++)
		for(W=Graph->G[V].FirstEdge;W;W=W->Next)
			if (V < W->Adjx) {/*避免重复录入无向图的边 只收V1<V2的边*/
				ESet[ECount].V1 = V;
				ESet[ECount].V2 = W->Adjx;
				ESet[ECount++].Weight = W->Weight;
			}
	/*初始化最小堆*/
	for (ECount = Graph->Ne / 2; ECount >= 0; ECount--)
		PerDown(ESet, ECount, Graph->Ne);
}
void Swap(struct ENode* a, struct ENode* b) {
	struct ENode* c;
	c = a;
	a = b;
	b = c;
}
/*给定当前堆的大小CurrentSize,将当前最小边位置弹出并调整*/
int GetEdeg(Edge ESet, int CurrentSize) {
	Swap(&ESet[0], &ESet[CurrentSize - 1]);/*将最小边与当前堆的最后一个位置的边交换*/
	PerDown(ESet, 0, CurrentSize - 1);/*将剩下的边继续调整成最小堆*/

	return CurrentSize - 1;/*返回最小边所在位置*/
}
int Kruskal(LGraph Graph, LGraph& MST) {
	WeightType TotalWeight;
	int ECount, NextEdge;
	SetType VSet;/*顶点数组*/
	Edge ESet;//边数组

	InitializeVSet(VSet, Graph->Nv);/*初始化顶点并查集*/
	ESet = (Edge)malloc(sizeof(struct ENode) * Graph->Ne);
	//ESet = new ENode[Graph->Ne];
	InitializeESet(Graph, ESet);/*初始化边的最小堆*/
	
	//创建MSV图
	MST = CreateGraph(Graph->Nv);
	TotalWeight = 0;
	ECount = 0;

	NextEdge = Graph->Ne;//原始边集合的规模
	while (ECount < Graph->Nv - 1) {//当收集的边下与顶点数-1时
		NextEdge = GetEdeg(ESet, NextEdge);
		if (NextEdge < 0)//边收集已经空
			break;
		if (ChekCycle(VSet, ESet[NextEdge].V1, ESet[NextEdge].V2))//如果不构成回来
		{
			// 插入边到MST中
			InsertEdge(MST, ESet + NextEdge);//相当于&ESet[NextEdge] ;
			TotalWeight += ESet[NextEdge].Weight;
			ECount++;
		}

	}//while循环结束 
	if (ECount < Graph->Nv - 1)
		TotalWeight = -1;//设置错误标准

		return TotalWeight;
}
void DFS(LGraph Graph, Vertex V) {
	cout << V << endl;
	PtrToAdjVNode W;
	Visited[V] = 1;
	for (W = Graph->G[V].FirstEdge; W; W = W->Next) {
		if (Visited[W->Adjx] == 0) {
			DFS(Graph, W->Adjx);
		}
	}

}
int main()
{
	LGraph Graph = BuildGraph();
	LGraph MST = NULL;
	Kruskal(Graph, MST);
	DFS(MST, 0);
	for(int i=0;i<Graph->Ne;i++)
		
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/929154.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

增量预训练网络安全大模型的一次尝试

一、背景 探索使用网络安全知识&#xff0c;对开源基模型进行增强&#xff0c;评估是否能使基模型在网络安全领域表现出更好地专业度。 项目基于云起无垠SecGPT开源项目&#xff0c;在hugeface开源数据集的基础上&#xff0c;增加了自有预训练数据&#xff0c;进行增量预训练…

从零开始配置 Docker 网络:快速掌握各类型网络的设置与使用场景

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 文章内容 📒📝 Docker 网络类型概述🎯 Bridge 驱动🎯 Host 驱动🎯 None 驱动🎯 Overlay 驱动🎯 Macvlan 驱动🔖 获取网络接口📝 总结:选择合适的网络类型⚓️ 相关链接 ⚓️📖 介绍 📖 如果你曾经在搭建…

C语言(一维数组练习)

键盘录入一组数列&#xff0c;利用冒泡排序将数据由大到小排序 #include <stdio.h>int main(int argc,char *argv[]) {int i,j,tmep;int arr[10];printf("请输入10个测试整数&#xff1a;\n");int lensizeof(arr)/sizeof(arr[0]);for(i0;i<len;i){scanf(&q…

PostgreSQL实现透视表查询

PostgreSQL 8.3版本发布时&#xff0c;引入了一个名为tablefunc的新扩展。这个扩展提供了一组非常有趣的函数。其中之一是交叉表函数&#xff0c;用于创建数据透视表。这就是我们将在本文中讨论的内容。 需求说明 解释此函数如何工作的最简单方法是使用带有数据透视表的示例…

消息中间件-Kafka1-实现原理

消息中间件-Kafka 一、kafka简介 1、概念 Kafka是最初由Linkedin公司开发&#xff0c;是一个分布式、支持分区&#xff08;partition&#xff09;、多副本的&#xff08;replica&#xff09;&#xff0c;基于zookeeper协调的分布式消息系统&#xff0c;它的最大的特性就是可以…

protobuf实现Hbase数据压缩

目录 前置HBase数据压缩效果获取数据(反序列化) 前置 安装说明 使用说明 HBaseDDL和DML操作 HBase数据压缩 问题 在上文的datain中原文 每次写入数据会写入4个单元格的内容&#xff0c;现在希望能对其进行筛减&#xff0c;合并成1格&#xff0c;减少存储空间&#xff08;序列…

爬虫专栏第二篇:Requests 库实战:从基础 GET 到 POST 登录全攻略

简介&#xff1a;本文聚焦 Requests 库的强大功能与应用实战。首先介绍其安装步骤及版本选择要点&#xff0c;随后深入讲解 GET 请求&#xff0c;以百度页面为例&#xff0c;展示如何发起基本 GET 请求、巧妙添加 headers 与参数以精准搜索&#xff0c;以及正确设置 encoding 避…

【Leetcode】19. 删除链表的第N个节点

【Leetcode】19. 删除链表的第N个节点 1. 题目介绍2. 方法一&#xff1a;计算链表长度逻辑流程:代码复杂度分析 1. 题目介绍 题目描述 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,…

工业齐套管理虚拟现实仿真模拟软件

工业齐套管理虚拟现实仿真模拟软件是与法国最大的汽车制造商合作开发的一款虚拟现实仿真模拟软件&#xff0c;借助身临其境的虚拟现实环境&#xff0c;无需停止生产线&#xff0c;即可模拟仓库和提货区域。 工业齐套管理虚拟现实仿真模拟软件不仅适用于汽车工业&#xff0c;安全…

【嘟嘟早教卡】 小程序源码分享带后台管理

【嘟嘟早教卡】是专门为 3-6 岁婴幼儿童学习普通话、英语研发的早教启蒙认知识字的小程序 小程序由 Taro 及 Tailwind CSS 构建而成&#xff0c;后台管理使用 Laravel 及 Tailwind CSS 想法源于小时候玩的认知卡片&#xff0c;基本大部分家庭都买过认知卡片&#xff0c;我按照…

概率论相关知识随记

作为基础知识的补充&#xff0c;随学随记&#xff0c;方便以后查阅。 概率论相关知识随记 期望&#xff08;Expectation&#xff09;期望的定义离散型随机变量的期望示例&#xff1a;掷骰子的期望 连续型随机变量的期望示例&#xff1a;均匀分布的期望 期望的性质线性性质期望的…

FastAPI 响应状态码:管理和自定义 HTTP Status Code

FastAPI 响应状态码&#xff1a;管理和自定义 HTTP Status Code 本文介绍了如何在 FastAPI 中声明、使用和修改 HTTP 状态码&#xff0c;涵盖了常见的 HTTP 状态码分类&#xff0c;如信息响应&#xff08;1xx&#xff09;、成功状态&#xff08;2xx&#xff09;、客户端错误&a…

oracle 11g中如何快速设置表分区的自动增加

在很多业务系统中&#xff0c;一些大表一般通过分区表的形式来实现数据的分离管理&#xff0c;进而加快数据查询的速度。分区表运维管理的时候&#xff0c;由于人为操作容易忘记添加分区&#xff0c;导致业务数据写入报错。所以我们一般通过配置脚本或者利用oracle内置功能实现…

机器学习深入剖析逻辑回归算法

一、引言 在机器学习领域&#xff0c;逻辑回归&#xff08;Logistic Regression&#xff09;是一种极为经典且应用广泛的算法。尽管其名称带有 “回归” 二字&#xff0c;但实际上它主要用于解决分类问题&#xff0c;并且在众多领域都发挥着重要作用。接下来&#xff0c;让我们…

如何加强游戏安全,防止定制外挂影响游戏公平性

在现如今的游戏环境中&#xff0c;外挂始终是一个困扰玩家和开发者的问题。尤其是定制挂&#xff08;Customized Cheats&#xff09;&#xff0c;它不仅复杂且隐蔽&#xff0c;更能针对性地绕过传统的反作弊系统&#xff0c;对游戏安全带来极大威胁。定制挂通常是根据玩家的需求…

6.824/6.5840 Lab 1: MapReduce

宁静的夏天 天空中繁星点点 心里头有些思念 思念着你的脸 ——宁夏 完整代码见&#xff1a; https://github.com/SnowLegend-star/6.824 由于这个lab整体难度实在不小&#xff0c;故考虑再三还是决定留下代码仅供参考 6.824的强度早有耳闻&#xff0c;我终于也是到了挑战这座高…

解决Jupyter Notebook无法转化为Pdf的问题(基于Typora非常实用)

笔者在完成各项作业和做笔记时&#xff0c;经常用到jupyter notebook&#xff1b;其因为可以同时运行python并提供格式化的数字公式的输入方式&#xff0c;得到了广大用户的喜爱。 当我们想要将.ipynb文件导出为pdf时&#xff0c;有两种常用方法。 1.Ctrlp 2.通过File ->…

[在线实验]-RabbitMQ镜像的下载与部署

镜像下载 docker的rabbitmq镜像资源-CSDN文库 加载镜像 docker load --input rabbitmq.tar 给镜像打标签 这里发现镜像名为none&#xff0c;需要给镜像重命名下 docker tag [镜像id] [新镜像名称]:[新镜像标签] docker tag ebaf409ffbe2 rabbitmq:management 运行镜像…

【JVM】—G1 GC日志详解

G1 GC日志详解 ⭐⭐⭐⭐⭐⭐ Github主页&#x1f449;https://github.com/A-BigTree 笔记链接&#x1f449;https://github.com/A-BigTree/Code_Learning ⭐⭐⭐⭐⭐⭐ 如果可以&#xff0c;麻烦各位看官顺手点个star~&#x1f60a; 文章目录 G1 GC日志详解1 G1 GC周期2 G1日…

ADBC 查询语法介绍:EXECUTE_QUERY

可使用 CL_SQL_STATEMENT 类的以下实例方法执行查询&#xff1a; EXECUTE_QUERY 该方法有一个字符串类型的强制输入参数 STATEMENT&#xff0c;必须向其传递语法正确的 SELECT 语句。与 DML 语句一样&#xff0c;SET_PARAM 方法可用于将 ABAP 数据对象绑定到占位符。 查询结…