图的应用1.0-----最小生成树问题

前言

生成树

1.基本概念

2.生成树的特点

3.生成树形成过程

最小生成树(Minimum Spanning Tree)

前言

今天我们学习图的应用，对于最小生成树问题，那什么是最小生成树呢？图又这么去实现一个生成树和最小生成树？下面我们就一起来看看。

数据结构----图的应用四部曲
最小生成树问题：图的应用1.0-----最小生成树问题-CSDN博客
最短通路问题（Djkstra算法）：图的应用2.0-----最短通路问题(Dijkstra和Floyd算法)-CSDN博客

拓扑排序：图的应用3.0-----拓扑排序-CSDN博客
关键路径算法：图的应用4.0-----关键路径(AOE网)-CSDN博客

生成树

1.基本概念

生成树:所有顶点均由边连接在一起，但不存在回路的图。

如上图所示，除了第一个不是生成树（因为存在环），其他都是生成树。

2.生成树的特点

图的生成树有以下特点：

一个图可以有许多棵不同的生成树
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图，去掉一条边则非连通
一个有n个顶点的连通图的生成树有n-1条边
在生成树中再加一条边必然形成回路。
生成树中任意两个顶点间的路径是唯一的

3.生成树形成过程

形成过程：

设图G=(V,E)是个连通图，当从图任一顶点出发遍历图G时，将边集E(G)分成两个集合T(G)和B(G)。其中T(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V,T)是图G的极小连通子图。即子图G1是连通图G的生成树。

最小生成树(Minimum Spanning Tree)

1.基本概念

最小生成树:给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。

如图所示，连通图的最小生成树权值之和为17才是最小生成树

2.构造方法（MST）

最小生成树（Minimum Spanning Tree），根据其英文名字有一个叫MST算法用于去构造最小生成树，MST算法本质是一种贪心算法，根据贪心算法的方式去获取到最优解。

MST 性质:设N= (V,E)是一个连通网，U是顶点集V的一个非空子集。若边(u, v)是一条具有最小权值的边，其中uEu,vEV-U，则必存在一棵包含边(u, v)的最小生成树。

MST解释说明：

在生成树的构造过程中，图中n个顶点分属两个集合:

已落在生成树上的顶点集:u ·已落在生成树上的顶点集：U
尚未落在生成树上的顶点集:V-U ·尚未落在生成树上的顶点集：V-U

接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边

下面我就介绍两种MST算法，分别是Prim算法和Kruskal算法。

以下代码是一个图的邻接矩阵创建代码：


#include
#include
#include
#define Maxint 32767
#define Maxnum 100//最大顶点数
 
 
//数据类型
typedef struct d {
	char id[10];
	//……
}
ElemType;
//图的邻接数组
typedef struct graph {
	ElemType vexs[Maxnum];//图数据
	int matrix[Maxnum][Maxnum];//二维数组
	int vexnum;//点数
	int arcnum;//边数
}Graph;
 
 
//节点id查找下标
int Locate_vex(Graph G, char* id) {
	for (int i = 0; i < G.vexnum; i++)
		if (strcmp(G.vexs[i].id, id) == 0)
			return i;
	return -1;
}
 
//构造邻接矩阵(无向图，对称矩阵)(有向图)赋权图
void Create_graph(Graph* G) {
	printf("请输入顶点个数和边的个数：\n");
	scanf("%d %d", &G->vexnum, &G->arcnum);//输入点数边数
	printf("请输入顶点数据:\n");
	for (int i = 0; i < G->vexnum; i++) {
		scanf("%s", G->vexs[i].id);
	}
	for (int x = 0; x < G->vexnum; x++) {
		for (int y = 0; y < G->vexnum; y++) {
			if (x == y)
				G->matrix[x][y] = 0;//对角线初始化为0
			else
				G->matrix[x][y] = Maxint;//其他初始化为Maxint
		}
	}
	printf("请输入边相关数据:\n");
	for (int k = 0; k < G->arcnum; k++) {
		char a[10], b[10];
		int w;
		scanf("%s %s %d", a, b, &w);
		//a->b
		int i = Locate_vex(*G, a);
		int j = Locate_vex(*G, b);
		//矩阵赋值
		G->matrix[i][j] = w;
		G->matrix[j][i] = w;//删掉这个，表示有向图
	}
}
 
//输出矩阵
void print_matrix(Graph G) {
	printf("矩阵为：\n");
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			if(G.matrix[i][j]==Maxint)
				printf("∞\t");
			else
				printf("%d\t", G.matrix[i][j]);
		}
		printf("\n");
	}
	printf("图的顶点个数和边数：%d,%d\n", G.vexnum, G.arcnum);
}
 
//遍历
void visit(Graph G, int loca) {
	printf("%s ", G.vexs[loca].id);
}

普里姆(Prime)算法

1.算法思想

Prime算法的核心步骤是：在带权连通图中V是包含所有顶点的集合， U已经在最小生成树中的节点，从图中任意某一顶点v开始，此时集合U={v}，重复执行下述操作：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边，将(u,w)这条边加入到已找到边的集合，并且将点w加入到集合U中，当U=V时，就找到了这颗最小生成树

其实，算法的核心步骤就是：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边。

过程如下图所示：

2.代码实现


							//最小生成树
//生成树
typedef struct shortedge {
	char adjvex_id[10];//储存到的数据id
	int lowcost;//到其他顶点最短路径距离
}ShortEdge;
//01---Prim算法							
//在U集合中找到距离其他顶点最近的下一个顶点位置
int min_path(Graph G, ShortEdge* shortedge) {
	int  location;
	int min = Maxint;
	for (int i = 1; i < G.vexnum; i++) {
		if (min > shortedge[i].lowcost && shortedge[i].lowcost != 0) {
			min = shortedge[i].lowcost;
			location = i;
		}
	}
	return location;
}
//Prim接口
void MST_Prim(Graph G, char* start) {
	printf("(Prim)最小生成树如下：\n");
 
	ShortEdge shortdege[Maxnum];//集合U
	int sum = 0;//统计最短路径权之和
	//对第一个起始数据start初始化处理，把第一个顶点放入到集合U当中
	int k = Locate_vex(G, start);
	//当前集合U只有顶点start，那么里面的数据就储存start的数据
	for (int i = 0; i < G.vexnum; i++) {
		strcpy(shortdege[i].adjvex_id, start);
		shortdege[i].lowcost = G.matrix[k][i];
	}
	shortdege[k].lowcost = 0;//此顶点对应的下标标记为0，表示已经加入集合U当中
 
	//后继处理
	for (int i = 0; i < G.vexnum-1; i++) {
		//找到下一个离集合U最近的顶点，下标为k
		k = min_path(G, shortdege);
		sum += shortdege[k].lowcost;
		printf("%s->%s %d\n", shortdege[k].adjvex_id, G.vexs[k].id, shortdege[k].lowcost);
		shortdege[k].lowcost = 0;//此顶点对应的下标标记为0，表示已经加入集合U当中
 
		//加入了新的顶点后，对集合U到其他顶点最近距离的值进行更新
		for (int j = 0; j < G.vexnum; j++) {
			if (G.matrix[k][j] < shortdege[j].lowcost && shortdege[j].lowcost!=0) {
				shortdege[j].lowcost = G.matrix[k][j];
				strcpy(shortdege[j].adjvex_id, G.vexs[k].id);
			}
		}
	}
	printf("最小生成树权之和为：%d\n", sum);
}

测试结果：


int main() {
	Graph G;
	Create_graph(&G);
	print_matrix(G);
 
	MST_Prim(G, "V1");
}

克鲁斯卡尔（Kruskal）算法

1.算法思想

克鲁斯卡尔算法是一种用于求解最小生成树问题的贪心算法。最小生成树是一个连通图的生成树，其边的权重之和最小。一、原理克鲁斯卡尔算法的核心思想是按照边的权重从小到大逐渐选择连通图的边，直到所有顶点都被连接为止。在每一步中，选择当前权重最小的边，若该边的两个顶点尚未连接，则将其添加到最小生成树的边集合中，并将这两个顶点归为同一个连通分量。克鲁斯卡尔（Kruskal）算法又称作为避圈法。

过程如下：

2.代码实现

这里就需要对边进行权值的大小排序，直接就用快速排序去进行排序，（头文件.h）如下:


#pragma once
//边的结构体数据
typedef struct edge {
	char begin_id[10];//边起点的id
	char end_id[10];//边终点的id
	int weight;//权值
}Edge;
void quick_sort(Edge* n, int left, int right);

快速排序源文件.c代码如下：


#include"sort.h"
//快速排序---递归实现
void quick_sort(Edge* n, int left, int right) {
	int i, j, temp;
	i = left;
	j = right;
	if (i > j) {
		return;
	}
	else {
		temp = n[left].weight;
		while (i != j) {
			while (n[j].weight >= temp && i < j)//先向左移动j
				j--;
			while (n[i].weight <= temp && i < j) //再向右移动i
				i++;
			if (i < j) {//此时对i和j指向的数字进行数字交换
				Edge num = n[i];
				n[i] = n[j];
				n[j] = num;
			}
		}//当i和j相遇的时候就结束循环
 
		//此时i与j相遇，就与temp交换
		Edge new_temp = n[i];
		n[i] = n[left];
		n[left] = new_temp;
	}
	//最后左右边依次进入到递归
	quick_sort(n, left, i - 1); //左边的数字都比temp要小
	quick_sort(n, i + 1, right);  //右边的数字都比temp要大
}

克鲁斯卡尔（Kruskal）算法代码如下：


						//最小生成树
 
//02--Kruskal算法
//对边排序
Edge* arc_sort(Graph G) {
	//创建边数据
	Edge* edge = (int*)malloc(sizeof(Edge) * G.arcnum);
 
	int count = 0;
	//把边的数据储存到edge里面（无向图）
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j <= i; j++) {
			if (G.matrix[i][j] != Maxint && G.matrix[i][j] != 0) {
				strcpy(edge[count].begin_id, G.vexs[i].id);
				strcpy(edge[count].end_id, G.vexs[j].id);
				edge[count].weight = G.matrix[i][j];
				count++;
			}
		}
	}
	//对边的权值进行排序
	quick_sort(edge, 0, count - 1);
	return edge;
}
 
//接口
void MST_Kruskal(Graph G) {
	Edge* edge = arc_sort(G);
	int sum = 0;
	int vset[Maxnum];//辅助数组判断连通性
	//初始化为01234……表示开始的时候都不连通
	for (int i = 0; i < G.vexnum; i++)
		vset[i] = i;
 
	for (int i = 0; i < G.arcnum; i++) {
		int a = Locate_vex(G, edge[i].begin_id);//a为起点顶点的位置下标
		int b = Locate_vex(G, edge[i].end_id);//b为这个边终点的位置下标
		int v1 = vset[a];//辅助数组中找到起点的连通标准
		int v2 = vset[b];//辅助数组中找到终点的连通标准
		//判断v1与v2是否相等，判定是否成环
		if (v1!=v2) {
			printf("%s——%s %d\n", edge[i].begin_id, edge[i].end_id, edge[i].weight);
			sum += edge[i].weight;
			for (int j = 0; j < G.vexnum; j++) {
				//与v1连通的数据全部改成v2，表示整体连通
				if (vset[j] == v1)
					vset[j] = v2;
			}
		}
	}
	printf("最小生成树的权值之和：%d\n", sum);
	//释放空间
	free(edge);
	edge = NULL;
}

测试结果：


int main() {
	Graph G;
	Create_graph(&G);
	print_matrix(G);
 
	MST_Kruskal(G);
}

Prime算法与Kruskal算法比较

以上就是本期的全部内容了，我们下一次见！

分享一张壁纸：

相关阅读:
SpringBoot整合MQ
算法与数据结构 --- 队列的表示和操作的实现
 【每日一题】1109. 航班预订统计
 聚美优品根据ID取商品详情 API
【IVI】15.1.2 系统稳定性优化篇（LMKD Ⅱ）PSI 压力失速信息
 卓越领先！安全狗入选2023年福建省互联网综合实力50强
 Flink_CDC搭建及简单使用
 刷题笔记19——优势洗牌和去重保持字典序
 微信小程序——数据绑定
 MATLAB算法实战应用案例精讲-【优化算法】A*算法
原文地址：https://blog.csdn.net/m0_73633088/article/details/134035900