[图论]Prim

Prim

• 本质：BFS+贪心，对点进行操作。与最短路Dijkstra算法是“孪生兄弟”。
• 存储结构：链式前向星
• 适用对象：可为负权图，可求最大生成树
• 核心思想：最近的邻接点一定在最小生成树(MST)上，对点的最近邻接点贪心。
• 算法流程：设源点$s$(任意点)，MST已选点集 { S } \set{S} {S}(初始 { S } = ∅ \set{S}=\varnothing {S}=∅)；各点当前到已选点集 { S } \set{S} {S}的最小边权 { d i s } \set{dis} {dis}(初始 { d i s } \set{dis} {dis}：非$s:+\infty$,表示该点目前不可达；$s=0$)；当前MST方案数组$tree$(存储其上个源点,初始化为$-1$表示无方案)，待算法结束后极为最终方案；当前轮起点$U$，$U$邻接点集 { V } \set{V} {V}，邻接点权值集 { W } \set{W} {W}。
  循环执行下列步骤，直到点集 { S } \set{S} {S}包含所有顶点，或剩余点无法进入 { S } \set{S} {S}：
  1. 考查最近顶点(贪心)：从全体点集中，找出先前不在 { S } \set{S} {S}中(未被考查)且距点集 { S } \set{S} {S}最近($dis$最小)的顶点，作为当前轮起点$U$(首次即为源点$s$)，将其进入 { S } \set{S} {S}(考查顶点$U$)
  2. 扩散邻接点(BFS扩散)：扩散$U$的邻接点且先前未被考查的顶点$V$，检查是否能通过$U$而使其距点集 { S } \set{S} {S}更短($dis$更小)。若更短，则更新该点$dis$，并更新路径：$dis[V]=min(dis[V],W)$,$tree[V]=U$
• Prim算法与最短路算法Dijkstra是“孪生兄弟”。与Dijkstra不同之处在于更新操作中，Prim为更新为所有点到 { S } \set{S} {S}整体的距离(即$dis[V]=min(dis[V],W)$)；而Dijkstra为更新所有点到 { S } \set{S} {S}中特定一点(源点$s$)的距离(即$dis[V]=min(dis[V],dis[U]+W)$)。
• 复杂度：朴素版$O(V^2)$，二叉堆优化版$O(V{\log }_{2}E)$

using ll=long long;
using pll=pair<ll,ll>;
const ll INF=__LONG_LONG_MAX__;
ll n,m,s;//点数,边数,源点
struct vertex{int e=-1;
}v[n];
struct edge{int u,v,w,n=-1;
}e[m];

注：若无特殊说明，本文默认顶点均为从0起编号。

朴素版

• 选目前$dis$最小点$U$的3个条件:该点未被考查,该点$dis$非无穷,该点$dis$更小
• 扩散至$U$邻接点$V$的3个条件:该邻接点未被考查,边权值$W$非无穷,$V$通过$U$而使$dis$更短

int prim() {vector<bool>S(n,0);vector<ll>dis(n,INF),tree(n,-1);ll s=0,ans=0;dis[s]=0;for (int j=0;j<n;j++){ll U=-1,minn=INF;for(ll i=0;i<n;i++)if(!S[i]&&dis[i]!=INF&&dis[i]<minn) U=i,minn=dis[i];if(U==-1) return -1;//剩余点均不可达,不存在MSTS[U]=1;ans+=dis[U];for (ll i=v[U].e;~i;i=e[i].n){//~i:i!=-1ll V=e[i].v,W=e[i].w;if (!S[V]&&W!=INF&&dis[V]>W)//与Dijkstra唯一不同点dis[V]=min(dis[V],W),tree[V]=U;}}return ans;
}

若求最大生成树：$dis$应初始化为$-\infty$；找$dis$最大顶点；更新条件改为$dis[V]<W$。

二叉堆优化版

优化点：另设顶点的小根堆$Q$，其结构为 { d i s , i n d e x } \set{dis,index} {dis,index}，可动态维护当前$dis$最小点$U$。

另设计数器$cnt$，若$cnt<V$，则证明是非连通图，无法构成MST。

• 选目前$dis$最小点$U$的3个条件:该点未被考查,该点$dis$非无穷,该点$dis$更小。

• 扩散至$U$邻接点$V$的3个条件:该邻接点未被考查,边权值$W$非无穷,$V$通过$U$而使$dis$更短

int prim() {vector<ll>dis(n,INF),tree(n,-1);vector<bool>S(n,0);priority_queue<pll,vector<pll>,greater<>>pq;int ans=0,cnt=0,s=0;dis[s]=0,pq.push({dis[s],s});//dis,indexwhile(pq.size()){ll U=pq.top().second;pq.pop();if(S[U]) continue;S[U]=1,ans+=dis[U],cnt++;for(ll i=v[U].e;~i;i=e[i].n){//~i:i!=-1ll V=e[i].v,W=e[i].w;if(!S[V]&&W!=INF&&dis[V]>W){//与Dijkstra唯一不同点dis[V]=W,tree[V]=U;pq.push({dis[V],V});}}}if(cnt<n) return -1;return ans;
}

若求最大生成树：$dis$应初始化为$-\infty$；维护大根堆；更新条件改为$dis[V]<W$。