【蓝桥杯--图论】最小生成树prim、kruskal

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

【蓝桥杯--图论】最小生成树prim、kruskal,数据结构与算法,蓝桥杯,图论,职场和发展
【蓝桥杯--图论】最小生成树prim、kruskal,数据结构与算法,蓝桥杯,图论,职场和发展

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


【蓝桥杯--图论】最小生成树prim、kruskal,数据结构与算法,蓝桥杯,图论,职场和发展

prim算法

#include <cstring>
#include <algorithm>
#include <iostream>

#define _CRT_SECURE_NO_WARNINGS
using namespace std;

const int N = 510,INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
	memset(dist, 0x3f, sizeof dist);

	int res = 0;

	for (int i = 0; i < n; i++)
	{
		int t = -1;
		for (int j = 1; j <= n; j++)
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;

		if (i && dist[t] == INF)return INF;
		if (i)res += dist[t];

		for (int j = 1; j <= n; j++)dist[j] = min(dist[j], g[t][j]);

		st[t] = true;
	}
	return res;
}

int main()
{
	scanf("%d%d", &n, &m);

	memset(g, 0x3f, sizeof g);

	while (m--)
	{
		int a, b,c;
		scanf("%d%d%d", &a, &b, &c);
		g[a][b] = g[b][a] = min(g[a][b], c);
	}
	int t = prim();

	if (t == INF)puts("impossible");
	else printf("%d\n", t);

	return 0;
}

kruskal算法(稀疏图)

#include <algorithm>
#include <iostream>

#define _CRT_SECURE_NO_WARNINGS
using namespace std;

const int N = 10010;

int n, m;
int p[N];

struct Edge
{
	int a, b, w;

	bool operator< (const Edge& W)const
	{
		return w < W.w;
	}
}edges[N];

int find(int x)
{
	if (p[x] != x)p[x] = find(p[x]);
	return p[x];
}

int main()
{
	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i++)
	{
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		edges[i] = { a,b,w };
	}

	sort(edges, edges + m);

	for (int i = 1; i <= n; i++)p[i] = i;

	int res = 0, cnt = 0;
	//res存储最小生成树中的权重之和
	//cnt存储的是当前存储了多少条边
	for (int i = 0; i < m; i++)
	{
		int a = edges[i].a, b = edges[i].b, w = edges[i].w;

		a = find(a), b = find(b);
		if (a != b)
		{
			p[a] = b;
			res += w;
			cnt++;
		}
	}

	if (cnt < n - 1)puts("impossible");
	else printf("%d\n", res);
	return 0;
}

【蓝桥杯--图论】最小生成树prim、kruskal,数据结构与算法,蓝桥杯,图论,职场和发展文章来源地址https://www.toymoban.com/news/detail-820518.html

到了这里,关于【蓝桥杯--图论】最小生成树prim、kruskal的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

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

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

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

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

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

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

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

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

    2024年02月05日
    浏览(58)
  • 最小(代价)生成树—Prim算法与Kruskal算法

    目录  一、最小生成树的特点 二、最小生成树算法  ① Prim(普里姆)算法 ②Kruskal(克鲁斯卡尔)算法  ③Prim算法与Kruskal算法对比 最小生成树是带权连通图G=(V,E)的生成树中边的权值之和最小的那棵生成树。它具有以下特点: 图G中各边权值互不相等时有唯一的最小生成树。图

    2024年02月01日
    浏览(38)
  • 【最小生成树】一文学懂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)
  • 求最小生成树Prim(普里姆)和Kruskal(克鲁斯卡尔)算法

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

    2024年02月05日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包