连通图：无向图中，任意两个顶点都有路径相通，称该无向图为连通图。
强连通图：有向图中，任意两个顶点都有路径相通，称该有向图为强连通图。
连通网：连通图的每条边对应一个数，称为权，称这种连通图叫做连通网。
生成树：连通图的一个连通子图，它含有全部n个顶点，但只有足以构成树的n-1条边。
最小生成树：连通网中的所有生成树中，边的代价和最小的生成树。
Prim算法：也称为‘加点法’，每次迭代选择代价最小的边对应的点，加入到最小生成树中。
1.图中所有顶点集合V；初始令集合u={s}，v=V-u；
2.在两个集合中u，v能够组成的边中，选择一条代价最小的边（u0,v0）,加入到最小生成树中，并把v0并入到集合u中；
3.重复上述步骤，直到最小生成树有n-1条边或者n个顶点。
#include<bits/stdc++.h>
using namespace std;
const int inf=999999999;
int n,m;
int e[111][111],vis[111],dis[111];
void init()
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) e[i][j]=0;
else e[i][j]=inf;
}
}
}
void prim(){
memset(vis,0,sizeof(vis));
vis[1]=1;
for(int i=1;i<=n;i++){
dis[i]=e[1][i];
}
int coun=1,sum=0,j,minn;
while(coun<n){
minn=inf;
for(int i=1;i<=n;i++){
if(vis[i]==0&&dis[i]<minn){
minn=dis[i];
j=i;
}
}
vis[j]=1;
coun++;
sum+=dis[j];
for(int k=1;k<=n;k++){
if(vis[k]==0&&dis[k]>e[j][k]){
dis[k]=e[j][k];
}
}
}
cout<<sum<<endl;
}
int main()
{
int u,v,w;
cin>>n>>m;
init();
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
e[u][v]=w;
e[v][u]=w;
}
prim();
}
Kruskal算法：也称‘加边法’，初始最小生成树边数为0，每迭代一次选择一条满足条件的最小代价边，加入到最小生成树集合中。
1.把图中所有边按照代价从小到大排序；
2.把图中的n个顶点看成独立的n棵树；
3.按权值从小到大选择边，所选的边连接的两个顶点应属于两棵不同的树，则成为生成树的一条边，并将两棵树合并作为一棵树。
4.重复（3），直到所有顶点都在一棵树上或者有n-1条边为止。
#include<bits/stdc++.h>
using namespace std;
int n,m,pre[111];
struct edge{
int u,v,w;
}e[111];
bool cmp(edge a,edge b){
return a.w<b.w;
}
void init(){
for(int i=1;i<=n;i++)
pre[i]=i;
}
int findd(int v){
if(pre[v]==v)
return v;
else{
pre[v]=findd(pre[v]);
return pre[v];
}
}
int mergee(int u,int v){
int a=findd(u);
int b=findd(v);
if(a!=b){
pre[b]=a;
return 1;
}
return 0;
}
int main ()
{
while(cin>>n>>m){
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
sort(e+1,e+1+m,cmp);
init();
int cont=0,sum=0;
for(int i=1;i<=m;i++){
if(mergee(e[i].u,e[i].v)){
cont++;
sum+=e[i].w;
}
if(cont==n-1) break;
}
cout<<sum<<endl;
}
}