当前位置： 首页 > article >正文

数据结构-最小生成树

article 2025/2/7 11:50:35

一.最小生成树的定义

从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;
}


http://www.kler.cn/a/417556.html

相关文章：

  • uniapp访问django目录中的图片和视频,2025[最新]中间件访问方式
  • 支持向量机（一）
  • 10. k8s二进制集群之Kube Scheduler部署
  • 图论常见算法
  • 【21天学习AI底层概念】day14 （kaggle新手入门教程）random forests
  • SpringBoot+SpringDataJPA项目中使用EntityManager执行复杂SQL
  • vue3+ant design vue实现日期选择器默认显示当前年，并限制用户只能选择当前年及之前~
  • Astra+ 深度相机系统架构解析：组件功能、数据流和应用领域
  • YOLO系列论文综述（从YOLOv1到YOLOv11）【第5篇：YOLOv3——多尺度预测】
  • JMeter中获取随机数、唯一ID、时间日期（包括当前日期增减）截取指定位数的字符等
  • 853 有边数限制的最短路(bellman-ford贝尔曼福特算法)
  • MySQL常见面试题（一）
  • A*（A-star）算法
  • qt QGraphicsEllipseItem详解
  • 电气火灾式故障电弧探测器在某医院照明回路中的应用
  • 第七课 Unity编辑器创建的资源优化_UI篇（UGUI）
  • Java中TimedCache缓存对象的详细使用
  • 力扣--LCR 149.彩灯装饰记录I
  • RAG数据拆分之PDF
  • Java Stream reduce 函数，聚合数据
  • html 中的 ＜code＞标签
  • uniapp的video组件截图（抓拍）功能，解决截后为黑图bug
  • MySQL中的锁与MVCC
  • 【Ansible】自动化运维工具
  • Kafka知识体系
  • Python面向对象编程与模块化设计练习