【图论】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)

---

四.【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;
}