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

蓝桥杯备考:图论之Prim算法

嗯。通过我们前面的学习,我们知道了,一个具有n个顶点的连通图,它的生成树包括n-1个边,如果边多一条就会变成图,少一条就不连通了

接下来我们来学一下把图变成生成树的一个算法

Prim算法,我们从任意一个结点开始构造最小生成树,先把离生成树最近的点拉进来,然后更新所有结点距离生成树的距离,然后再拉进来最近的点,然后再更新所有结点到这颗生成树的距离,一直到所有结点全部拉进来的时候,我们的算法就结束了

这里我们需要开两个数组,一个是dist数组来判断某个点距离生成树的距离,另一个是st数组,来判断某个点在不在生成树里

如图,我们把起始点加入进去了,接下来我们更新一下所有点离最小生成树的距离

我们还是找距离生成树最近的结点,如图,是5,我们把5拉进去

接下来把5标记上,然后更新所有点距离最小生成树的距离

然后继续找最小的,应该是2结点了

把2结点拉进去之后,我们再次更新dist数组,....如此往复,直到所有点都遍历完之后,我们的最小生成树也就构建完了;

话不多说我们来实现一下代码

我们先来实现一下邻接矩阵的代码;

这道题我们还要考虑一下连通不连通的情况

比如这张图,当我们用prim算法把2,1,5,4都加到生成树里的时候,3这个结点距离生成树的值还是无穷,就说明他不连通,没法找最小生成树

下面就是我们的代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010;
const int INF = 0x3f3f3f3f;
int dist[N];
bool st[N];
int edges[N][N];
int n, m;
int ret = 0;
int prim()
{
	dist[1] = 0;
	for (int i = 1; i <= n; i++)//循环把n个结点加入到生成树里面 
	{
		//1.找最近点
		int t = 0;
		for (int j = 1; j <= n; j++)
		{
			if (dist[j] < dist[t] && !st[j])
			{
				t = j;
			}
		}
		if (dist[t] == INF) return INF;//不连通
		//把最小结点加入到生成树里
		st[t] = true;
		ret += dist[t];
		//更新所有结点离最小生成树的距离
		for (int i = 1; i <= n; i++)
		{
			dist[i] = min(dist[i], edges[t][i]);
		}
	}
	return ret;
}
int main()
{
	cin >> n >> m;
	memset(dist, 0x3f, sizeof(dist));
	memset(edges, 0x3f, sizeof(edges));
	for (int i = 1; i <= m; i++)
	{
		int a, b, c; cin >> a >> b >> c;
		edges[a][b] = edges[b][a] = min(edges[a][b],c);
	}
	ret = prim();
	if (ret == INF) cout << "orz" << endl;
	else cout << ret << endl;





	return 0;
}

接下来,我们用邻接表实现一下这道题

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 5010, INF = 0x3f3f3f3f;
vector <PII> path[N];
int dist[N];
bool st[N];
int ret = 0;
int n, m;
int prim()
{
	dist[1] = 0;
	for (int i = 1; i <= n; i++)
	{
		int t = 0;
		for (int j = 1; j <= n; j++)
		{
			if (dist[t] > dist[j] && !st[j])
			{
				t = j;
			}
		}
		if (dist[t] == INF) return INF;
		st[t] = true;
		ret += dist[t];
		for (auto &e : path[t])
		{
			int x = e.first, y = e.second;
			dist[x] = min(dist[x], y);
		}
	}
	return ret;
}
int main()
{
	memset(dist, 0x3f, sizeof(dist));
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, z; cin >> x >> y >> z;
		path[x].push_back({ y,z });
		path[y].push_back({ x,z });
	}
	int r = prim();
	if (r == INF) cout << "orz" << endl;
	else cout << r << endl;






	return 0;
}

根据我们的代码可以看到,我们的prim算法时间复杂度是N²,如果结点很少边很多的话,我们用prim算法最合适


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

相关文章:

  • 分类操作-06.根据id删除分类
  • python 打印阳历对应的日农历时间
  • .gitignore 文件用于 Git 应忽略的文件夹的格式
  • SNX币合规交易突破 XBIT去中心化交易所引领DEX安全新范式
  • Notepad++插件:快捷选择成对括号之间的内容
  • 【SpringMVC】常用注解:@RequestHeader
  • WEB UI自动化测试中,元素定位的八大定位方式详解
  • docker,centos容器开机启动程序
  • 手搓排列型枚举递归搜索树 全排列问题(dfs)
  • 南邮大一统计学想转码,考研还是就业?如何避免就业被卡?转专业难度大吗?是CC++或Java?
  • 深度学习多模态人脸情绪识别:从理论到实践
  • 提升fcp
  • “Ubuntu禁止root用户通过SSH直接登录”问题的解决
  • docker容器导出导入
  • soulip属地怎么不是我当前的位置
  • 【开原宝藏】30天学会CSS - DAY1 第一课
  • 前端缓存接口数据
  • 4、linux c 进程
  • Django系列教程(8)——函数视图及通用类视图
  • 仿“东方甄选”直播商城小程序运营平台