建站宝盒源码,山东济南seo整站优化公司,网站建设的参考文献,网站手机端优化一.介绍 Prim算法是一种用于解决最小生成树问题的贪心算法。最小生成树问题是指在一个连通无向图中找到一个生成树#xff0c;使得树中所有边的权重之和最小。
Prim算法的基本思想是从一个起始顶点开始#xff0c;逐步扩展生成树#xff0c;直到覆盖所有顶点。具体步骤如下…一.介绍 Prim算法是一种用于解决最小生成树问题的贪心算法。最小生成树问题是指在一个连通无向图中找到一个生成树使得树中所有边的权重之和最小。
Prim算法的基本思想是从一个起始顶点开始逐步扩展生成树直到覆盖所有顶点。具体步骤如下
选择一个起始顶点作为生成树的根节点并将其加入生成树中。从生成树中的顶点出发选择一条与生成树相连的边中权重最小的边并将其加入生成树中。重复步骤2直到生成树包含了所有顶点。
Prim算法的关键在于如何选择与生成树相连的边中权重最小的边。一种常用的方法是使用优先队列最小堆来存储候选边每次选择权重最小的边加入生成树。
Prim算法的时间复杂度为O(ElogV)其中V是顶点数E是边数。它是一种有效的算法适用于稠密图和稀疏图。 二.Prim与Dijkstra
其实Prim算法和Dijkstra算法差不多就是一点小的改进分别在第293233行。
29统计sum数量若sumn说明无法构成最小树因为构成最小树的点都不够
32,33wdis[v]即可因为只需要点到点不是点到起点. 三.题目
P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 四.【AC】代码
#includebits/stdc.h
#define maxn 200005
#define inf 0x7fffffff
using namespace std;
int n,m,ans0,sum0;
int head[5001],dis[5001];
bool vis[maxn],flag0;
//链式前向星
struct Edge{int u,v,w,next;
}edge[maxn1]; //无向图要*2
int cnt0;
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.ww;}
};
void Prim(){for(int i2;in;i) dis[i]inf;dis[1]0;priority_queuenode q;q.push((node){1,0});while(!q.empty()){node tempq.top();q.pop();int utemp.u;if(vis[u]) continue;vis[u]1;sum;anstemp.w;for(int ihead[u];i;iedge[i].next){int vedge[i].v,wedge[i].w;if(wdis[v]){dis[v]w;q.push((node){v,dis[v]});}}}
}
int main(){//输入数据 cinnm;for(int i1;im;i){int u,v,w;cinuvw;add(u,v,w);add(v,u,w);}//调用算法 Prim();//输出答案if(sumn) coutans;else coutorz; return 0;
}
