以前写的是Kruskal算法实现最小生成树，这次添加Prim算法
上次没有介绍最小生成树，这次一起添加吧
而且没有电路的有向图被称为树
给定无向图，你可以根据无向图来种树。 这就是图的生成树。 图的生成树可能有多个
当这个无向图为连通的赋权图时，在无向图的所有生成树中，必然存在一个边的权值和最小的生成树，被称作最小生成树
最小生成树的性质也再看一下
3358 www.Sina.com/http://www.Sina.com/kruskal和Prim算法其实是基于贪婪的，但kruskal算法必须首先对对边权重进行排序。 Prim算法每次都选择当前权重最小的边
最小生成树不能形成回路
1 .定义I=0，U=空集合，从连通图G={V，E}中的一个顶点u中选择具有最小相关权重的边(u，v )，并将该顶点添加到生成树的顶点集合u中
2 .以后，各步骤在一个顶点位于u而另一个顶点不位于u的各边缘中，从选择权值最小的边缘(u，v )开始，将该顶点追加到集合u、I中
如果i=n - 1，则算法结束。 否则，请转至步骤2并选择另一条边
基于前一种保存方法链式前向星可以写Prim算法的代码
在这里，我们使用优先队列进行了优化
最小生成树模板
ll ans； int n，m，num，cnt； int vis[maxn]，dis[maxn]； int head[maxn]； typedef pair int，int pii； priority_queuepii、vector pii、greater pii q； //优先队列优化记录边权和下一个节点struct node //链前锋星{ int to； int val； 下一步； }E[maxn*2]； voidadd(intu、int v、int w ) { cnt； E[cnt].to=v； E[cnt].val=w； E[cnt].next=head[u]； head[u]=cnt； }void Prim () q.push ) make_pair ) ) 0，1 )； while (！ q.empty(numn ) { int d=q.top ).first； int u=q.top ().second； q.pop (； if(vis[u] ) continue； ans =d； num； //找到边vis[u]=1标记后，我的边已经for(intI=head[u]； I； I=e [ I ].next ] if (e [ I ].valdis [ e [ I ].to ] ) /如果当前边缘权较小，则更新dis[E[i].to]=E[i].val； q.push(make_pair(e[I].val，E[i].to ) )； //对新的边界和节点进行排队} }}int main () STD :3360 IOs 33603360 sync _ with _ stdio (false )； CIN.Tie(0)，cout.tie(0) ) 0； for(intI=1； imaxn； I ) dis[i]=0x3f3f3f3f； //初始化距离最大cin n m； for(intI=0； im； I ) { int u，v，w； cin u v w； add(u，v，w )； 添加(v，u，w )； //无有向图} Prim (； n==num？ cout ans endl : cout 'orz' endl； 返回0； }当然，也有一些版本经过优化，但没有优先队列。 我也放在这里
int n，m，now，num，cnt，ans； int vis[maxn]、dis[maxn]、head[maxn]； //标记排列最短距离head排列structedge(//链式前锋int to； int val； 下一步； (}E[maxn]； voidadd(intu、int v、int w ) /内存映射{ cnt； E[cnt].next=head[u]； E[cnt].to=v； head[u]=cnt； E[cnt].val=w； (}int Prim ) ) {now=1； for(intI=2； i=n； I ) dis[i]=0x3f3f3f3f； //初始化距离最大为for(intI=head[1]； I！=0； I=e[I].next(/1顶点至dis[E[i].to]=min(e[I].val，dis[e[I].to] )； //寻找边权最小点while(numn-1 ) intminn=0x3f3f3f； vis[now]=1； //因为确定了第一个点，所以标记for (inti=1； i=n； I ) If (最小Ndis [ I ]！ vis[I]}{minn=dis[I]； now=i； } } ans =minn； num； //边加for (inti=head [ now ]； I！=0； I=e[I].next(//当前起点为nowif ) dis[e].to ) e[I].val！ vis [ e [ I ].to ] (dis [ e [ I ].to ]=e [ I ].val； } }返回Ans； (}int main ) ) {io n m； for(intI=0； im； I ) {int u，v，w； io u v w； add(u，v，w )； 添加(v，u，w )； //无有向图}printf('%dn '，Prim ) )； 返回0； }