【【贪心算法】最小生成树】（带全无向连通）图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。
1.Prim算法
主要思想：Prim是先选出一个源点，将它放入已选集合中，从与已选集合中的点相连，且另一点没有被选中的权值最小的边，将这个点也放入已选集合中，重复之前的步骤。每一次循环都会找到一条边，所以循环进行verNum-1次。
//6 101 2 61 3 11 4 52 3 52 5 33 4 53 5 63 6 44 6 25 6 6
//9 141 2 41 8 82 3 82 8 113 4 73 6 43 9 24 5 94 6 145 6 106 7 27 8 17 9 68 9 7
#include
using namespace std;
#define MAX_V 5005
#define MAX 0x7fffff
int verNum,edgeNum,sum=0;
int edge[MAX_V][MAX_V];
int pre[5005];
//数组用于临时存储当前选中边的另一个端点，每次输出选中情况后更新为-1不在参与接下来的工作
void Prim()
{
int *dist=new int[verNum+1];
//数组从1开始，防RE
for(int i=1;
i<=verNum;
i++)
{
dist[i]=edge[1][i];
pre[i]=1;
}
pre[1]=-1;
//以1作为源点
for(int i=1;
i"<>verNum>>edgeNum;
for(int i=1;
i<=verNum;
i++)
for(int j=1;
j<=i;
j++)
edge[i][j]=edge[j][i]=MAX;
for(int i=1;
i<=edgeNum;
i++)
{
int a,b,c;
cin>>a>>b>>c;
edge[b][a]=edge[a][b]=min(c,edge[a][b]);
//洛谷防重边
}
Prim();
bool flag=true;
for(int i=1;
i<=verNum;
i++)
if(pre[i]!=-1)
{
flag=false;
break;
}
if(flag==true)
cout< 2.Kruskal算法
主要思想：Kruskal主要是利用了查并集的思想，先将边按从小到大排列，然后从权值小的开始，如果边的两个端点不在一个集合就可以输出，然后将它们合并到一个集合中。
#include
#include
#include
using namespace std;
//6 101 2 61 3 11 4 52 3 52 5 33 4 53 5 63 6 44 6 25 6 6
//9 141 2 41 8 82 3 82 8 113 4 73 6 43 9 24 5 94 6 145 6 106 7 27 8 17 9 68 9 7
int vertexnum,edgenum;
//点的总数和边的总数
int root[5005],ans=0;
//记录每个点的上级
struct Graphic
{
int weight;
//权重
int x;
int y;
}g[200005];
bool cmp(Graphic a,Graphic b)
{
return a.weight "<>vertexnum>>edgenum;
for(int i=1;
i<=vertexnum;
i++)
root[i]=i;
for(int i=1;
i<=edgenum;
i++)
cin>>g[i].x>>g[i].y>>g[i].weight;
sort(g,g+edgenum+1,cmp);
//按权重从小到大排序
kruskal();
int i;
for(i=1;
i
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 数据结构与算法|数据结构与算法——绪论
- 算法（动态规划（更新中））
- NLP 中文形近字相似度算法开源实现
- cnn|基于卷积神经网络的人脸识别算法
- leetcode|Leetcode 191. Number of 1 Bits (Python)
- 算法与模型研究|实体识别NER——BiLSTM+CRF知识总结与代码（Pytorch）分析——细粒度实体的识别（基于CLUENER）
- 神仙|B2. Tokitsukaze and Good 01-String (hard version)
- #yyds干货盘点#项目实战 <-; DeepSORT算法实现车辆和行人跟踪计数和是否道路违规检测
- 『数据结构与算法』栈（原理与实现）