Prim算法是一种贪心算法，用于从图中找到最小生成树。Prim算法找到包含图的每个顶点的边的子集，从而可以最小化边的权重之和。
Prim的算法从单个节点开始，并在每一步探索所有具有所有连接边的相邻节点。选择了具有最小权重的边，导致图中没有循环。
Prim算法的工作原理
算法的目的是找到全局最优值。从一个顶点开始，不断添加权重最低的边，直到找到目标。
Prim算法的实现步骤如下：
1、用随机选择的顶点初始化最小生成树。
2、找到将树连接到新顶点的所有边，找到最小值并将其添加到树中。
3、继续重复步骤2，直到得到最小生成树。
Prim算法的实现
简单地选择权重为1的边。在下一次迭代中，我们有三个选项，权重为2、3和4的边。因此，我们将选择权重为2的边并标记顶点。现在我们再次有三个选项，权重为3、4和5的边。但我们不能选择权重为3的边，因为它正在创建一个循环。所以我们将选择权重为4的边，最终得到总成本为7的最小生成树（=1+2+4）。
using namespace std;
const int MAX=1e4+5;
typedef pair<long long,int>PII;
bool marked[MAX];
vector<PII>adj[MAX];
long long prim(int x){
priority_queue<PII,vector<PII>,greater<PII>>Q;
int y;
long long minimumCost=0;
PII p;
Q.push(make_pair(0,x));
while(!Q.empty())
{
p=Q.top();
Q.pop();
x=p.second;
if(marked[x]==true)
continue;
minimumCost+=p.first;
marked[x]=true;
for(int i=0;i<adj[x].size();++i)
{
y=adj[x]<i>.second;
if(marked[y]==false)
Q.push(adj[x]<i>);
}
}
return minimumCost;}
int main(){
int nodes,edges,x,y;
long long weight,minimumCost;
cin>>nodes>>edges;
for(int i=0;i<edges;++i)
{
cin>>x>>y>>weight;
adj[x].push_back(make_pair(weight,y));
adj[y].push_back(make_pair(weight,x));
}
minimumCost=prim(1);
cout<<minimumCost<<endl;
return 0;}Prim算法和Kruskal算法的区别
Prim算法
1、从图中的任何顶点构建最小生成树
2、遍历一个节点不止一次以获得最小距离
3、Prim算法给出了连通分量，并且它只适用于连通图
4、Prim算法在密集图中运行得更快
5、从根顶点开始生成最小生成树
6、Prim算法更适合列表数据结构
Kruskal算法
1、从图中权重最小的顶点开始构建最小生成树
2、只遍历一个节点一次
3、Kruskal算法可以在任何时刻生成森林，也可以在断开的组件上工作
4、Kruskal算法在稀疏图中运行得更快
5、从权重最小的边开始生成最小生成树
6、Kruskal的算法更喜欢堆数据结构
