做房产网站接不到电话,网站建设问卷调查,中铁建设集团有限公司是国企吗,淘宝关键词排名查询网站目录 最小生成树prim
最小生成树算法是一种用来在一个加权连通图中找到最小生成树的算法。最小生成树是一个包含图中所有顶点的树#xff0c;其总权值最小。
prim算法
洛谷题目示例
P3366 【模板】最小生成树
题目描述
输入格式
输出格式
输入输出样例
说明/提示
题…目录 最小生成树prim
最小生成树算法是一种用来在一个加权连通图中找到最小生成树的算法。最小生成树是一个包含图中所有顶点的树其总权值最小。
prim算法
洛谷题目示例
P3366 【模板】最小生成树
题目描述
输入格式
输出格式
输入输出样例
说明/提示
题目分析
代码示例 最小生成树prim
最小生成树算法是一种用来在一个加权连通图中找到最小生成树的算法。最小生成树是一个包含图中所有顶点的树其总权值最小。
常见的最小生成树算法包括
1. Prim算法从一个顶点开始每次选择与当前生成树最近的顶点加入生成树中直到所有顶点都被加入。Prim算法的时间复杂度为O(V^2)或O(ElogV)其中V为顶点数E为边数。
2. Kruskal算法将所有边按权值从小到大排序依次加入生成树中但要保证加入的边不会形成环。Kruskal算法的时间复杂度为O(ElogE)或O(ElogV)其中V为顶点数E为边数。
这两种算法都可以用来求解最小生成树选择哪种算法取决于具体情况和图的规模。 这里主要讲解第一种算法
prim算法
Prim算法是一种用来在加权连通图中找到最小生成树的贪心算法。算法的基本思想是从一个初始顶点开始逐步扩展生成树每次选择与当前生成树最近的顶点加入生成树中直到所有顶点都被加入。
具体步骤如下
1. 选择一个初始顶点作为生成树的根节点并将其加入生成树中。 2. 从生成树中的所有顶点出发找到与生成树中的顶点相连且权值最小的边将其连接的顶点加入生成树。 3. 重复上述步骤直到所有顶点都被加入生成树为止。
Prim算法的时间复杂度取决于如何实现最小堆数据结构通常为O(V^2)或O(ElogV)其中V为顶点数E为边数。Prim算法适用于稠密图或边的数量接近顶点数的情况。
总的来说Prim算法是一种简单且有效的算法用来求解加权连通图的最小生成树问题。
洛谷题目示例
P3366 【模板】最小生成树
题目描述
如题给出一个无向图求出最小生成树如果该图不连通则输出 orz。
输入格式
第一行包含两个整数 N,M表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 Xi,Yi,Zi表示有一条长度为 Zi 的无向边连接结点 Xi,Yi。
输出格式
如果该图连通则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。
输入输出样例
输入 #1复制
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出 #1复制
7
说明/提示
数据规模
对于 20%的数据N≤5M≤20。
对于 40% 的数据N≤50M≤2500。
对于 70%的数据N≤500M≤104。
对于 100%100% 的数据1≤N≤50001≤M≤2×1051≤Zi≤104。
样例解释 所以最小生成树的总边权为 2237
题目分析 1模板题不过注意测试数据存在平行边如果用邻接矩阵存图的话应该存最短的平行边。
代码示例
#includebits/stdc.h
using namespace std;
#define Maxr 5001
int n,m;
int mp[Maxr][Maxr];
bool vis[Maxr];
int dist[Maxr];
int Prim()
{int sum0;memset(dist,0x7f,sizeof(dist));vis[1]true;for(int i1; in; i)dist[i]mp[1][i];//首先把第一个顶点录入所以下一个循环是infor(int i1; in; i)//由于第一个顶点已经录入权值所以循环n-1次{int minn0x7f7f7f7f,minj0;for(int j1; jn; j){if(!vis[j]dist[j]minn)//未走过的节点中权最小的节点的位置{minndist[j];minjj;}}if(!minj)return -1;summinn;//累加提前避免闭环vis[minj]true;for(int j1; jn; j){ //依次更新后面没走过的点的权最小值if(!vis[j])dist[j]min(dist[j],mp[minj][j]);}}return sum;
}
int main()
{memset(mp,0x7f,sizeof(mp));cinnm;for(int i0; im; i){int x,y,z;cinxyz;mp[x][y]mp[y][x]min(mp[x][y],z);//邻接矩阵存图}int sumPrim();if(sum-1)coutorzendl;else coutsumendl;return 0;}
如果以上有啥问题还望大佬能指正下哈
