2023年8月1日发(作者：)
prim和kruskal算法区别（低配版）prim和kruskal算法区别洛⾕P3366 最⼩⽣成树板⼦题主要区别：Dijkstra和Prim算法区别：Dijkstra已经选中了⼀个点，只剩下n-1次；Prim并未选中任何点这篇博客介绍两个算法：Prim算法和Kruskal算法，两个算法各有优劣⼀般来说当图⽐较稀疏的时候，Kruskal算法⽐较快⽽当图很密集，Prim算法就⼤显⾝⼿了下⾯是这两种算法的介绍Prim算法好吧，其实当我第⼀眼看到这个东西的时候感觉和Dijkstra好像，但是学了之后发现其实区别还是很明显（并且好记）的Dijkstra是维护从到源点的最短长度，⽽Prim则是维护到最⼩⽣成树的最短长度（其实就是到最⼩⽣成树上所有点的最短长度）那么Prim到底是什么呢？Prim的思想是将任意节点作为根，再找出与之相邻的所有边（⽤⼀遍循环即可），再将新节点更新并以此节点作为根继续搜，维护⼀个数组：dis，作⽤为已⽤点到未⽤点的最短距离。Prim算法之所以是正确的，主要基于⼀个判断：对于任意⼀个顶点v，连接到该顶点的所有边中的⼀条最短边(v, vj)必然属于最⼩⽣成树（即任意⼀个属于最⼩⽣成树的连通⼦图，从外部连接到该连通⼦图的所有边中的⼀条最短边必然属于最⼩⽣成树）举个栗⼦：图⽚莫名消失，只有代码了。。。（以后从新整理⼀篇）#include
int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans;//dis数组表⽰当前点到最⼩⽣成树的最短路径
bool vis[maxn];inline void add_edge(int from,int to,int value){ edge[++cnt].to=to; edge[cnt]._dis=value; edge[cnt].next=head[from]; head[from]=cnt;}//添加边
inline int prim(){ rep(i,2,n) dis[i]=inf;//初始化
for(int i=head[1];i;i=edge[i].next)//遍历当前节点的每⼀条出边
dis[edge[i].to]=min(dis[edge[i].to],edge[i]._dis);//重边の处理
while(++tot { int minn=inf;//初始化min vis[now]=1;//已经到达 rep(i,1,n) if(!vis[i]&&minn>dis[i])//寻找到最⼩⽣成树距离最短的节点 minn=dis[i],now=i;//更新 ans+=minn;//更新最⼩⽣成树 for(int i=head[now];i;i=edge[i].next)//遍历每⼀条出边 { int to=edge[i].to; if(dis[to]>edge[i]._dis&&!vis[to]) dis[to]=edge[i]._dis;//更新dis数组 } } return ans;}int main(){ n=read(),m=read(); rep(i,1,m) { int from=read(),to=read(),value=read(); add_edge(from,to,value);//因为是⽆向图 add_edge(to,from,value);//双倍存储，双倍快乐 } cout< struct Edge{ int from,to,_dis;}edge[maxm];int fa[maxn],n,m,ans,eu,ev,cnt;//father数组⽤来存储⽗亲节点 bool cmp(Edge a,Edge b){ return a._dis }inline int find_die(int x){ while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x;//找爹 } inline int kruskal(){ sort(edge+1,edge+1+m,cmp);//先将所有的边按权值排序 rep(i,1,m) { eu=find_die(edge[i].from); ev=find_die(edge[i].to);//分别找始点和终点的祖宗节点 if(eu==ev)//如果是⼀个祖宗，就说明他们在⼀个联通图中 continue; ans+=edge[i]._dis;//更新最⼩⽣成树长度 fa[ev]=eu;//顺便标记⽗亲 if(++cnt==n-1)//知道⽣成最⼩⽣成树 break; } return ans;}int main(){ n=read(),m=read(); rep(i,1,n) fa[i]=i;//初始化⾃⼰是⾃⼰的⽗亲 rep(i,1,m) edge[i].from=read(),edge[i].to=read(),edge[i]._dis=read(); cout< struct Edge{ int from,to,_dis;}edge[maxm];int fa[maxn],n,m,ans,eu,ev,cnt;//father数组⽤来存储⽗亲节点 bool cmp(Edge a,Edge b){ return a._dis }inline int find_die(int x){ while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x;//找爹 }int main(){ n=read(),m=read(); rep(i,1,n) fa[i]=i;//初始化⾃⼰是⾃⼰的⽗亲 rep(i,1,m) edge[i].from=read(),edge[i].to=read(),edge[i]._dis=read(); sort(edge+1,edge+1+m,cmp);//先将所有的边按权值排序 rep(i,1,m&&cnt<=n-1) { eu=find_die(edge[i].from); ev=find_die(edge[i].to);//分别找始点和终点的祖宗节点 if(eu==ev)//如果是⼀个祖宗，就说明他们在⼀个联通图中 continue; ans+=edge[i]._dis;//更新最⼩⽣成树长度 fa[ev]=eu;//顺便标记⽗亲 cnt++; } if(cnt!=n-1) cout<<"orz"; else cout< 2023年8月1日发(作者：) prim和kruskal算法区别（低配版）prim和kruskal算法区别洛⾕P3366 最⼩⽣成树板⼦题主要区别：Dijkstra和Prim算法区别：Dijkstra已经选中了⼀个点，只剩下n-1次；Prim并未选中任何点这篇博客介绍两个算法：Prim算法和Kruskal算法，两个算法各有优劣⼀般来说当图⽐较稀疏的时候，Kruskal算法⽐较快⽽当图很密集，Prim算法就⼤显⾝⼿了下⾯是这两种算法的介绍Prim算法好吧，其实当我第⼀眼看到这个东西的时候感觉和Dijkstra好像，但是学了之后发现其实区别还是很明显（并且好记）的Dijkstra是维护从到源点的最短长度，⽽Prim则是维护到最⼩⽣成树的最短长度（其实就是到最⼩⽣成树上所有点的最短长度）那么Prim到底是什么呢？Prim的思想是将任意节点作为根，再找出与之相邻的所有边（⽤⼀遍循环即可），再将新节点更新并以此节点作为根继续搜，维护⼀个数组：dis，作⽤为已⽤点到未⽤点的最短距离。Prim算法之所以是正确的，主要基于⼀个判断：对于任意⼀个顶点v，连接到该顶点的所有边中的⼀条最短边(v, vj)必然属于最⼩⽣成树（即任意⼀个属于最⼩⽣成树的连通⼦图，从外部连接到该连通⼦图的所有边中的⼀条最短边必然属于最⼩⽣成树）举个栗⼦：图⽚莫名消失，只有代码了。。。（以后从新整理⼀篇）#include int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans;//dis数组表⽰当前点到最⼩⽣成树的最短路径 bool vis[maxn];inline void add_edge(int from,int to,int value){ edge[++cnt].to=to; edge[cnt]._dis=value; edge[cnt].next=head[from]; head[from]=cnt;}//添加边 inline int prim(){ rep(i,2,n) dis[i]=inf;//初始化 for(int i=head[1];i;i=edge[i].next)//遍历当前节点的每⼀条出边 dis[edge[i].to]=min(dis[edge[i].to],edge[i]._dis);//重边の处理 while(++tot { int minn=inf;//初始化min vis[now]=1;//已经到达 rep(i,1,n) if(!vis[i]&&minn>dis[i])//寻找到最⼩⽣成树距离最短的节点 minn=dis[i],now=i;//更新 ans+=minn;//更新最⼩⽣成树 for(int i=head[now];i;i=edge[i].next)//遍历每⼀条出边 { int to=edge[i].to; if(dis[to]>edge[i]._dis&&!vis[to]) dis[to]=edge[i]._dis;//更新dis数组 } } return ans;}int main(){ n=read(),m=read(); rep(i,1,m) { int from=read(),to=read(),value=read(); add_edge(from,to,value);//因为是⽆向图 add_edge(to,from,value);//双倍存储，双倍快乐 } cout< struct Edge{ int from,to,_dis;}edge[maxm];int fa[maxn],n,m,ans,eu,ev,cnt;//father数组⽤来存储⽗亲节点 bool cmp(Edge a,Edge b){ return a._dis }inline int find_die(int x){ while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x;//找爹 } inline int kruskal(){ sort(edge+1,edge+1+m,cmp);//先将所有的边按权值排序 rep(i,1,m) { eu=find_die(edge[i].from); ev=find_die(edge[i].to);//分别找始点和终点的祖宗节点 if(eu==ev)//如果是⼀个祖宗，就说明他们在⼀个联通图中 continue; ans+=edge[i]._dis;//更新最⼩⽣成树长度 fa[ev]=eu;//顺便标记⽗亲 if(++cnt==n-1)//知道⽣成最⼩⽣成树 break; } return ans;}int main(){ n=read(),m=read(); rep(i,1,n) fa[i]=i;//初始化⾃⼰是⾃⼰的⽗亲 rep(i,1,m) edge[i].from=read(),edge[i].to=read(),edge[i]._dis=read(); cout< struct Edge{ int from,to,_dis;}edge[maxm];int fa[maxn],n,m,ans,eu,ev,cnt;//father数组⽤来存储⽗亲节点 bool cmp(Edge a,Edge b){ return a._dis }inline int find_die(int x){ while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x;//找爹 }int main(){ n=read(),m=read(); rep(i,1,n) fa[i]=i;//初始化⾃⼰是⾃⼰的⽗亲 rep(i,1,m) edge[i].from=read(),edge[i].to=read(),edge[i]._dis=read(); sort(edge+1,edge+1+m,cmp);//先将所有的边按权值排序 rep(i,1,m&&cnt<=n-1) { eu=find_die(edge[i].from); ev=find_die(edge[i].to);//分别找始点和终点的祖宗节点 if(eu==ev)//如果是⼀个祖宗，就说明他们在⼀个联通图中 continue; ans+=edge[i]._dis;//更新最⼩⽣成树长度 fa[ev]=eu;//顺便标记⽗亲 cnt++; } if(cnt!=n-1) cout<<"orz"; else cout<
发布评论