最小生成树算法之Kruskal算法(c++)

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

与Prim算法生成图的最小生成的树算法不同在于:

Prim算法是基于图中的顶点的,且不依赖于边,Prim从顶点出发拓展,依次找每个顶点相邻的权值最小的边,直至生成最小生成树。因此,Prim算法的时间复杂度是O(v^2),适合边稠密图。

而Kruskal算法恰恰相反,是基于图中的边的一种算法,Kruskal算法的思想是:

从图中所有的边中依次选出权值最小的边,同时选出边两端的顶点,直至构成一个最小生成树。使用这种思想构建最小生成树,就会用到并查集判断当前的边时候还能添加进最小生成树。

Kruskal的算法核心代码:

void Kruskal(road *R, int* v, int n) {
	int a, b;
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		a = GetRoad(v,R[i].begin);
		b = GetRoad(v,R[i].end);
		if (a != b)
		{
			v[a] = b;
			sum += R[i].weight;
		}
	}
	cout << endl << sum;
}

并查集的算法核心代码:

int GetRoad(int *v, int p) {
	while (p != v[p])
	{
		p = v[p];
	}
	return p;
}

完整代码:

#include<iostream>
using namespace std;
#define MAX 4
typedef struct EdgeNode {
	int adjvex;
	int weight;
	EdgeNode* next;
};
typedef struct VexNode {
	char data;
	EdgeNode* first;
};
typedef struct Graph {
	VexNode GraphList[MAX];
	int vexnum;
	int edgenum;
};
typedef struct road {
	int begin;
	int end;
	int weight;
};
void CreatGraph(Graph &G) {
	int i, j, w;
	EdgeNode* e = NULL;
	EdgeNode* q = NULL;
	cout << "请输入顶点数和变数: " << endl;
	cin >> G.vexnum >> G.edgenum;
	cout << "请输入顶点信息: " << endl;
	for (int k = 0; k < G.vexnum; k++)
	{
		cin >> G.GraphList[k].data;
		G.GraphList[k].first = NULL;
	}
	for (int k = 0; k < G.edgenum; k++)
	{
		cout << "请输入边(vi,vj)的下标i,j以及权值: " << endl;
		cin >> i >> j >> w;
		e = new EdgeNode;
		e->weight = w;
		e->adjvex = j;
		e->next = G.GraphList[i].first;
		G.GraphList[i].first = e;
		/*q = new EdgeNode;
		q->weight = w;
		q->adjvex = i;
		q->next = G.GraphList[j].first;
		G.GraphList[j].first = q;*/
	}
}
void myprint(Graph G) {
	cout << "输入的邻接表图如下:" << endl;
	EdgeNode* p;
	for (int i = 0; i < G.vexnum; i++)
	{
		cout << G.GraphList[i].data << " ";
		for (p = G.GraphList[i].first; p; p = p->next)
		{
			cout << p->adjvex << " ";
		}
		cout << endl;
	}
}
void Sort(road* R,int n)
{
	int temp,tbe,ten;
	int min = R[0].weight;
	int flag = 0;
	int i, j;
	for ( i = 1; i < n; i++)
	{
		if (R[i].weight < R[i - 1].weight)
		{
			temp = R[i].weight;
			tbe = R[i].begin;
			ten = R[i].end;
			for (j = i - 1; temp < R[j].weight; j--)
			{
				R[j + 1].weight = R[j].weight;
				R[j + 1].begin = R[j].begin;
				R[j + 1].end = R[j].end;
			}
			R[j + 1].weight = temp;
			R[j + 1].begin = tbe;
			R[j + 1].end = ten;
		}
	}
}
void creatRoad(Graph G, road* R) {
	int j = 0;
	for (int i = 0; i < G.vexnum; i++)
	{
		EdgeNode* p = NULL;
		for (p = G.GraphList[i].first; p; p = p->next)
		{
			R[j].begin = i;
			R[j].end = p->adjvex;
			R[j].weight = p->weight;
			j++;
		}
	}
}
int GetRoad(int *v, int p) {
	while (p != v[p])
	{
		p = v[p];
	}
	return p;
}
void Kruskal(road *R, int* v, int n) {
	int a, b;
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		a = GetRoad(v,R[i].begin);
		b = GetRoad(v,R[i].end);
		if (a != b)
		{
			v[a] = b;
			sum += R[i].weight;
		}
	}
	cout << endl << sum;
}
int main() {
	int v[MAX];
	for (int i = 0; i < MAX; i++)
	{
		v[i] = i;
	}
	Graph G;
	CreatGraph(G);
	road R[100];
	//myprint(G);
	creatRoad(G, R);
	Sort(R, G.edgenum);
	cout << "Kruskal:" << endl;
	Kruskal(R, v, G.edgenum);
	return 0;
}

执行结果:

我构建的图:

kruskal算法c++程序,数据结构,算法,c++,图论,数据结构

 

kruskal算法c++程序,数据结构,算法,c++,图论,数据结构

注意:

对于并查集算法是可以进行优化减少时间复杂度的。 文章来源地址https://www.toymoban.com/news/detail-518957.html

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

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

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

相关文章

  • Kruskal 算法 最小生成树

    1.按边从小到大进行排序 2.从小到大进行加边,保证加入的边的两端点不连通,即保证不形成回路

    2024年02月10日
    浏览(38)
  • 最小生成树——Kruskal算法

    目录 基本思想 实现 伪代码 实际问题求解 最小生成树 :带权连通图的生成树中 边的权值之和最小的生成树。 最小生成树不是唯一的。当图中的各边权值互不相等时,最小生成树是唯一的; 若无向连通图本身是一棵树时(边数比顶点数少1 ),则最小生成树就是它本身。 最

    2023年04月26日
    浏览(47)
  • Kruskal算法求解最小生成树

    最小生成树是一个连通图。 什么是连通图,(强)连通图详解 前面介绍了《图存储结构》,本节继续讲解什么是 连通图 。 前面讲过,图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图 1 中,虽然 V1 和 V3 http://c.biancheng.net/view/3405.ht

    2024年02月07日
    浏览(54)
  • 最小生成树——Kruskal算法详解

    1.Kruskal算法解决问题 :最小生成树 2.Kruskal所需要的前提知识: 边集数组(引用)和 结构体 3.Kruskal算法主要思想: Kruskal算法将 n 个点看成 n 个独立的连通分支。 首先按边权大小排序。 然后只要在 m 条边里按 下表从小到大遍历 选出 合适 的 n - 1 条(前提条件:选出的边不

    2024年02月03日
    浏览(40)
  • 最小生成树(Prim算法,Kruskal算法)

    (1)生成树: 如果在一个无向连通图不包含回路(连通图中不存在环),则为一个树 (2)最小生成树(minimal spanning tree): 在一个图所有生成树中,代价最小的生成树称为最小生成树 (3)生成树的代价: 在一个无向连通网中,生成树各边的权值之和称为该生成树的代价

    2024年02月08日
    浏览(43)
  • 859. Kruskal算法求最小生成树

    给定一个 nn 个点 mm 条边的无向图,图中可能存在重边和自环,边权可能为负数。 求最小生成树的树边权重之和,如果最小生成树不存在则输出  impossible 。 给定一张边带权的无向图 G=(V,E)G=(V,E),其中 VV 表示图中点的集合,EE 表示图中边的集合,n=|V|n=|V|,m=|E|m=|E|。 由

    2023年04月09日
    浏览(38)
  • 图的最小生成树-Kruskal算法

    目录 问题引入  程序设计  程序分析 本节文章 【问题描述】 编写程序,利用带权无向图的邻接矩阵存储,实现图的最小生成树Kruskal算法。

    2024年02月08日
    浏览(57)
  • 最小生成树(Prim算法与Kruskal算法)

    一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边。我们把构造连通网的最小代价生成树称为最小生成树。 例如下图中①、②、③都是左侧图的生成树,但③是构造连通网的最小代价,所以③是该图的最小生成树。 P

    2024年02月05日
    浏览(57)
  • 最小生成树—Kruskal算法和Prim算法

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

    2024年02月05日
    浏览(46)
  • 图论13-最小生成树-Kruskal算法+Prim算法

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

    2024年02月01日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包