最小生成树(Prim算法,Kruskal算法)

这篇具有很好参考价值的文章主要介绍了最小生成树(Prim算法,Kruskal算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.概念

(1)生成树:如果在一个无向连通图不包含回路(连通图中不存在环),则为一个树

(2)最小生成树(minimal spanning tree):在一个图所有生成树中,代价最小的生成树称为最小生成树

(3)生成树的代价:在一个无向连通网中,生成树各边的权值之和称为该生成树的代价

如何处理点集,使得最小权值的边构成生成树?

1)从一个点出发,依次加入点形成点集(Prim)
2)从边出发,将点集合并,避免形成环(Kruskal)

2.Prim算法

1.思路

将所有顶点分成两个集合,一个是已经加入最小生成树的集合U,一个未加入的集合的V-U,基本过程可以如下描述:(下图来自懒猫老师的《数据结构》相关课程笔记)

(1)先选定一个开始构建最小生成树的结点编号,将选定的结点加入U,其他结点在V-U中

最小生成树(Prim算法,Kruskal算法)

(2) 寻找和该顶点连接的边的最小权值的结点,加入U中

最小生成树(Prim算法,Kruskal算法)

(3) 寻找U中所有结点连接的最小权值的边的结点,(如果有两个结点都和该结点相连,选取权值最小的一条,舍去另一条),并将其加入U中,重复进行,直至所有结点都加入U中

最小生成树(Prim算法,Kruskal算法)

(4)所有结点加入U中,结束

最小生成树(Prim算法,Kruskal算法)

2.数据结构

(1)图的存储:为便于读取任意两顶点之间的权值,采用邻接矩阵存储

(2)shortEdge[n]候选最短边集,包含adjvex和lowcost两个域,分别表示候选最短边的邻接点和权值(lowcost==0代表加入U中)

(3)用prim算法起始点初始化shortEdge[n]数组,后续添加结点过程中,与邻接矩阵中的值比较,再进行修改

最小生成树(Prim算法,Kruskal算法)

3.代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTEX 10//最大的顶点个数
typedef int DataType;

//无向图
typedef struct PrimNode {
	int adjvex;//某一点的前序点
	int lowcost;//若该顶点已经属于最小生成树集合U中则赋值0;
	//否则值为最小生成树集合U到该点的最小距离(权值);
} PrimNode;

void MGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum, int arcNum) { //初始化构造图(邻接矩阵法)
	printf("请逐个输入顶点的内容:");
	DataType x;
	DataType vi, vj, ave; //构建邻接矩阵时,一条边的两个结点编号
	for (int i = 0; i < vertexNum; i++) { //顶点数组赋值
		scanf("%d", &x);
		vertex[i] = x;
	}
	for (int i = 0; i < vertexNum; i++) //初始化邻接矩阵
		for (int j = 0; j < vertexNum; j++)
			arc[i][j] = INT_MAX;//赋值正无穷
	int count = 1;
	for (int i = 0; i < arcNum; i++) { //依次输入每一条边
		printf("请输入第%d条边依附的两个顶点的编号和权值:", count++);
		scanf("%d %d %d", &vi, &vj, &ave); //输入该边依附的顶点的编号
		arc[vi][vj] = ave; //赋值权值
		arc[vj][vi] = ave;
	}
}

void Prim(int arc[][MAX_VERTEX], int vertexNum, int start, PrimNode *shortEdge) {
	int k;
	for (int i = 0; i < vertexNum; i++) {//利用初始结点,初始化辅助数组shortEdge
		shortEdge[i].lowcost = arc[start][i];
		shortEdge[i].adjvex = start;
	}
	shortEdge[start].lowcost = 0; //代表该点已经属于最小生成树集合U了
	for (int i = 0; i < vertexNum - 1; i++) {//循环找
		k = minEdge(shortEdge, vertexNum); //寻找最短边的邻接点k
		outputSMT(k, shortEdge, vertexNum); //输出最小生成树路径
		shortEdge[k].lowcost = 0; //将顶点k加入到集合U中
		for (int j = 0; j < vertexNum; j++) { //调整数组shortEdge[n]
			if (arc[k][j] < shortEdge[j].lowcost) {
				shortEdge[j].lowcost = arc[k][j];
				shortEdge[j].adjvex = k; //标明来自哪个邻接点
			}
		}
	}

}

void outputSMT(int k, PrimNode *shortEdge) {
	printf("(%d,%d)%d\n", shortEdge[k].adjvex, k, shortEdge[k].lowcost);
}

int minEdge(PrimNode *shortEdge, int vertexNum) {
	int min, flag = 0, index;
	for (int i = 0; i < vertexNum; i++) {
		if (shortEdge[i].lowcost != 0) {
			if (flag == 0) {
				min = shortEdge[i].lowcost;
				index = i;
				flag = 1;
			} else if (min > shortEdge[i].lowcost) {
				min = shortEdge[i].lowcost;
				index = i;
			}
		}
	}
	return index;
}

void printMGraph(DataType *vertex, int arc[][MAX_VERTEX], int vertexNum) { //输出
	printf("vertex:");
	for (int i = 0; i < vertexNum; i++) {
		printf("%d ", vertex[i]);
	}
	printf("\n");
	printf("arc:\n");
	for (int i = 0; i < vertexNum; i++) {
		for (int j = 0; j < vertexNum; j++) {
			if (j == vertexNum - 1) {
				if (arc[i][j] == INT_MAX)
					printf("  *\n");
				else
					printf(" %d\n", arc[i][j]);
			} else {
				if (arc[i][j] == INT_MAX)
					printf("  * ");
				else
					printf(" %d ", arc[i][j]);
			}
		}
	}

}

main() {
	DataType vertex[MAX_VERTEX];//储存所有的顶点
	int arc[MAX_VERTEX][MAX_VERTEX];//邻接矩阵,结点间的连通关系
	int vertexNum, arcNum; //顶点个数,边的个数
	printf("请输入顶点个数和边的个数:");
	scanf("%d %d", &vertexNum, &arcNum);
	MGraph(vertex, arc, vertexNum, arcNum);
	printf("输出邻接矩阵信息:\n");
	printMGraph(vertex, arc, vertexNum);
	int x;
	printf("请输入Prim算法的起点:");
	scanf("%d", &x);
	PrimNode shortEdge[vertexNum];
	printf("输出起点从编号%d开始的最小生成树:\n", x);
	Prim(arc, vertexNum, x, shortEdge);
}

4.输出测试

最小生成树(Prim算法,Kruskal算法)

2.Kruskal算法

1.思路

每次选出一条最短边,如果它和当前最小生成树不构成回路就将其加入最小生成树,否则将其删除,直到所有边都处理完毕,基本过程可以如下描述:

(1)将所有的边按照权值从小到大排序,并将所有的结点都看作一棵树,这里要重新定义图的存储

(2)依次将边从小到大加入生成树中

最小生成树(Prim算法,Kruskal算法)

 (3)若新加入的边会使已有树生成回路,则舍去

最小生成树(Prim算法,Kruskal算法)

2.数据结构  

(1)图的存储:Kruskal算法要求要从小到大的访问边的权值,邻接矩阵和邻接表都显得较麻烦,则需要定义一种新的储存结构,如下:

#define MAX_VERTEX 10//最多顶点个数
#define MAX_EDGE 100//最多边个数
typedef struct EdgeType {
	int from, to; //边依附的两个顶点
	int weight;//边上的权值
} EdgeType;

struct EdgeGraph {
	DataType vertex[MAX_VERTEX];//存放图顶点的数据
	EdgeType edge[MAX_EDGE];//存放边的数组
	int vertexNum, edgeNum; //图的顶点数和边数
};

 (2)parent[n]储存所有结点的双亲,若parent[i]==-1,代表该结点为根结点;若一个边相连的两个结点的parent数组的值相同,则代表连接这两个点会形成环,否则就可以合并加入生成树中,同时重新给parent数组赋值

3.代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_VERTEX 10//最多顶点个数
#define MAX_EDGE 100//最多边个数
typedef int DataType;

typedef struct EdgeType {
	int from, to; //边依附的两个顶点
	int weight;//边上的权值
} EdgeType;

struct EdgeGraph {
	DataType vertex[MAX_VERTEX];//存放图顶点的数据
	EdgeType edge[MAX_EDGE];//存放边的数组
	int vertexNum, edgeNum; //图的顶点数和边数
};

main() {
	int vertexNum, arcNum; //顶点个数,边的个数
	printf("请输入顶点个数和边的个数:");
	scanf("%d %d", &vertexNum, &arcNum);
	struct EdgeGraph graph;
	Graph(&graph, vertexNum, arcNum);
	ranklist(&graph);
	printf("输出通过边信息储存的图:\n");
	printGraph(graph);
	int parent[vertexNum];//每一个结点的双亲结点(根结点)
	printf("输出Kruskal算法得的最小生成树(from,to)weght:\n");
	Kruskal(graph, parent);
}

void Graph(struct EdgeGraph *graph, int vertexNum, int arcNum) {
	graph->edgeNum = arcNum;
	graph->vertexNum = vertexNum;
	printf("请逐个输入顶点的内容:");
	DataType x;
	for (int i = 0; i < vertexNum; i++) { //顶点数组赋值
		scanf("%d", &x);
		graph->vertex[i] = x;
	}
	int count = 1;
	int a, b, ave;
	for (int i = 0; i < arcNum; i++) { //依次输入每一条边
		printf("请输入第%d条边依附的两个顶点的编号和权值:", count++);
		scanf("%d %d %d", &a, &b, &ave); //输入该边依附的顶点的编号
		graph->edge[i].from = a;
		graph->edge[i].to = b;
		graph->edge[i].weight = ave;
	}
}

void ranklist(struct EdgeGraph *graph) { //将图的边数组按边的权值从小到大排序
	EdgeType temp;
	for (int i = 0; i < graph->edgeNum ; i++) { //冒泡排序
		for (int j = 0; j < graph->edgeNum  - i - 1; j++) {
			if (graph->edge[j].weight > graph->edge[j + 1].weight) {
				temp = graph->edge[j];
				graph->edge[j] = graph->edge[j + 1];
				graph->edge[j + 1] = temp;
			}
		}
	}
}

void Kruskal(struct EdgeGraph graph, int *parent) {
	for (int i = 0; i < graph.vertexNum; i++)
		parent[i] = -1; //初始化双亲数组,值为-1代表本身为根结点
	int num, i, vex1, vex2;
	for (num = 0, i = 0; i < graph.edgeNum; i++) {
		vex1 = findRoot(parent, graph.edge[i].from); //找到所在生成树的根结点
		vex2 = findRoot(parent, graph.edge[i].to); //找到所在生成树的根结点
		if (vex1 != vex2) { //找到的两个根结点不同,不会构成环
			outputMST(graph.edge[i]);//输出加入的边
			parent[vex2] = vex1; //合成生成树
			num++;
			if (num == graph.vertexNum - 1) //循环了“图的顶点数-1”次,提前返回
				return;
		}

	}
}

int findRoot(int *parent, int v) {
	int t = v;
	while (parent[t] > -1)
		t = parent[t]; //求顶点t上的双亲直达根结点
	return t;
}

void outputMST(EdgeType x) {
	printf("(%d,%d)%d\n", x.from, x.to, x.weight);
}

void printGraph(struct EdgeGraph graph) {
	printf("   no     from   to   weight\n");
	for (int i = 0; i < graph.edgeNum; i++) {
		printf("  edge[%d]  %d      %d      %d\n", i, graph.edge[i].from, graph.edge[i].to, graph.edge[i].weight);
	}
}

 4.输出测试

最小生成树(Prim算法,Kruskal算法)

初学小白,有错误的话欢迎指正!文章来源地址https://www.toymoban.com/news/detail-478600.html

到了这里,关于最小生成树(Prim算法,Kruskal算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论13-最小生成树-Kruskal算法+Prim算法

    基本思想:按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路 具体做法:首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中 不产生 回路,直至森林变成一棵树为止。 2.2.1 如果图不联通,直接返回空,该

    2024年02月01日
    浏览(50)
  • 最小生成树Kruskal、Prim算法C++

    连通图: 在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1和顶点v2是连通的。如果图中任意一对顶点都是连通的,则称此图为连通图。 生成树: 一个连通图的最小连通子图称作为图的生成树。有 n个顶点 的连通图的生成树有 n个顶点和 n-1 条边。 最小生成树: 最小生活

    2024年02月10日
    浏览(41)
  • 【最小生成树】一文学懂prim、kruskal算法

    博主简介: 努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。 博主主页: @是瑶瑶子啦 所属专栏: 算法 ;该专栏专注于蓝桥杯和ACM等算法竞赛🔥 近期目标: 写好专栏的每一篇文章 首先,我们要了解什么是最小生

    2023年04月25日
    浏览(32)
  • 用prim和kruskal算法求最小生成树问题

    题目 http://ybt.ssoier.cn:8088/problem_show.php?pid=1350 信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn) http://ybt.ssoier.cn:8088/problem_show.php?pid=1391 相当于一个图中求最小生成树的问题 prim解决 kruskal解法 信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn) http://ybt.ssoier.cn:8088/problem_show.ph

    2024年02月09日
    浏览(38)
  • C语言实现最小生成树算法:Prim和Kruskal

    以下是使用C语言实现Prim算法生成最小生成树的代码: 注释如下: #include stdio.h 和 `#include #define V 5 定义了图中顶点的个数为5。 int minDistance(int dist[], int visited[]) 函数用于找到顶点集合中未访问的顶点中距离最小的顶点。输入参数 dist 用于存储顶点到最小生成树的距离,输入

    2024年02月03日
    浏览(42)
  • 【算法基础:搜索与图论】3.5 求最小生成树算法(Prim&Kruskal)

    最小生成树 有关树的定义 生成子图 :生成子图是从原图中选取部分节点以及这些节点之间的边所组成的图。生成子图中的所有节点和边都必须在原图中存在。 生成树 :一个连通 无向图 的 生成子图 ,同时要求是树。也即在图的边集中选择 n - 1 条,将所有顶点连通。 我们

    2024年02月16日
    浏览(40)
  • 求最小生成树Prim(普里姆)和Kruskal(克鲁斯卡尔)算法

     想求最小生成树,我们首先得弄懂以下几个概念   连通图 :图中任意两个顶点都是连通的 极小连通子图 :既要保持图连通又要使得边数最少的子图 生成树 : 包含图中全部顶点的一个极小连通子图 连通图用通俗的话来讲就是,某一个顶点,可以 直接或者间接 (通过其他顶点

    2024年02月05日
    浏览(45)
  • 【数据结构与算法】最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

      🌱博客主页:大寄一场. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 一、最小生成树的概念 二、最小生成树的求解方法 三、练习题 四、最小生成树在实际应用中的例子 最近非科班的同学学到了最小生成树并询问我,于是想趁

    2024年02月07日
    浏览(42)
  • 【蓝桥杯--图论】最小生成树prim、kruskal

    今日语录: 成功不是终点,失败不是致命,勇气才是取胜的关键。

    2024年01月24日
    浏览(50)
  • 【刷题】图论——最小生成树:Prim、Kruskal【模板】

    假设有n个点m条边。 Prim适用于邻接矩阵存的稠密图,时间复杂度是 O ( n 2 ) O(n^2) O ( n 2 ) ,可用堆优化成 O ( n l o g n ) O(nlogn) O ( n l o g n ) 。 Kruskal适用于稀疏图,n个点m条边,时间复杂度是 m l o g ( m ) mlog(m) m l o g ( m ) 。 Prim:遍历n次,每次选择 连通块和外面的点 到连通块距离

    2024年04月13日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包