【图论】Prim算法

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

一.介绍

【图论】Prim算法,图论,图论,算法

 Prim算法是一种用于解决最小生成树问题的贪心算法。最小生成树问题是指在一个连通无向图中找到一个生成树,使得树中所有边的权重之和最小。

Prim算法的基本思想是从一个起始顶点开始,逐步扩展生成树,直到覆盖所有顶点。具体步骤如下:

  1. 选择一个起始顶点作为生成树的根节点,并将其加入生成树中。
  2. 从生成树中的顶点出发,选择一条与生成树相连的边中权重最小的边,并将其加入生成树中。
  3. 重复步骤2,直到生成树包含了所有顶点。

Prim算法的关键在于如何选择与生成树相连的边中权重最小的边。一种常用的方法是使用优先队列(最小堆)来存储候选边,每次选择权重最小的边加入生成树。

Prim算法的时间复杂度为O(ElogV),其中V是顶点数,E是边数。它是一种有效的算法,适用于稠密图和稀疏图。


 二.Prim与Dijkstra

其实Prim算法和Dijkstra算法差不多,就是一点小的改进,分别在第29,32,33行。

29:统计sum数量,若sum<n,说明无法构成最小树,因为构成最小树的点都不够!

32,33:w<dis[v]即可,因为只需要点到点,不是点到起点.


三.题目:

P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)文章来源地址https://www.toymoban.com/news/detail-618230.html


四.【AC】代码 

#include<bits/stdc++.h>
#define maxn 200005
#define inf 0x7fffffff
using namespace std;
int n,m,ans=0,sum=0;
int head[5001],dis[5001];
bool vis[maxn],flag=0;
//链式前向星
struct Edge{
	int u,v,w,next;
}edge[maxn<<1]; //无向图,要*2
int cnt=0;
void add(int u,int v,int w){
	edge[++cnt]=(Edge){u,v,w,head[u]};head[u]=cnt;
} 
struct node{
	int u,w;
	bool operator < (const node &x) const{return x.w<w;}
};
void Prim(){
	for(int i=2;i<=n;i++) dis[i]=inf;
	dis[1]=0;
	priority_queue<node> q;
	q.push((node){1,0});
	while(!q.empty()){
		node temp=q.top();q.pop();
		int u=temp.u;
		if(vis[u]) continue;
		vis[u]=1;sum++;ans+=temp.w;
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].v,w=edge[i].w;
			if(w<dis[v]){
				dis[v]=w;
				q.push((node){v,dis[v]});
			}
		}
	}
}
int main(){
	//输入数据 
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);
	}
	//调用算法 
	Prim();
	//输出答案
	if(sum==n) cout<<ans;
	else cout<<"orz"; 
	return 0;
}

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

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

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

相关文章

  • 搜索与图论:Prim

    每次将离连通部分的最近的点和点对应的边加入的连通部分,连通部分逐渐扩大,最后将整个图连通起来,并且边长之和最小。

    2024年02月08日
    浏览(44)
  • 【刷题】图论——最小生成树: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日
    浏览(43)
  • 【蓝桥杯--图论】最小生成树prim、kruskal

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

    2024年01月24日
    浏览(47)
  • 考研算法复试刷题19天:Prim算法求最小生成树 【prim,最小生成树】

    参考博客:图解:什么是最小生成树? - 知乎 (zhihu.com)  总结下来的过程就是,一张图,我们将他化为树的形式,也就是生成树。那么最小生成树有是啥呢? 所谓一个 带权图 的最小生成树,就是原图中边的权值最小的生成树 ,所谓最小是指边的权值之和小于或者等于其它

    2024年02月07日
    浏览(60)
  • 贪心算法:最小生成树Prim算法

    👨‍🎓作者简介:一位喜欢写作,计科专业大二菜鸟 🏡个人主页:starry陆离 🕒首发日期:2022年5月31日星期二 🌌上期文章:动态规划:多重背包问题 📚订阅专栏:算法分析与设计 如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦 这是大一暑假的c笔记,再一次写pri

    2024年02月01日
    浏览(50)
  • prim算法(普里姆算法)详解

    了解了什么是最小生成树后,本节为您讲解如何用普里姆(prim)算法查找连通网(带权的连通图)中的最小生成树。 普里姆算法查找最小生成树的过程,采用了贪心算法的思想。对于包含 N 个顶点的连通网,普里姆算法每次从连通网中找出一个权值最小的边,这样的操作重

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

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

    2024年02月08日
    浏览(42)
  • 实验13 prim算法和kruskal算法

    🔑一个神奇的哔哩哔哩讲解链接 🔑笔记补充——第十七章:贪婪算法(思想同,但应用上和伪代码略有差别) 使用prim算法实现最小生成树 输入 第一行两个整数n,e。n ( 1 ≤ n ≤ 200000 1 leq n leq 200000 1 ≤ n ≤ 200000 ) 代表图中点的个数,e ( 0 ≤ m ≤ 500000 0 leq m leq 500000 0 ≤

    2024年02月04日
    浏览(35)
  • 最小生成树—Prim算法

    我们要讨论的问题是如何在一个 无向图 中找到它的最小生成树,虽然这个问题对有向图也有意义,但是处理起来更麻烦。 一个无向图 G 的最小生成树就是连接 G 上所有顶点的边构成的树,且这些边的总权值最低。当且仅当图是 连通的 才有最小生成树。 在无向图的最小生成

    2024年02月09日
    浏览(46)
  • Prim算法

    前置知识 :图的概念与性质 为了保证学习效果,请保证已经掌握前置知识之后,再来学习本章节!如果在阅读中遇到困难,也可以回到前面章节查阅。 通过前面的学习,对于含有 n 个顶点的连通图来说可能包含有多种生成树,例如图 1 所示: 图 1 连通图的生成树 图 1 中的

    2024年02月02日
    浏览(27)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包