最小生成树即在加权连通图里寻找n-1条边，连接n个顶点，并且使得所有边的权重之和最小。最小生成树常用的算法有prim算法和kruskal算法。

1. prim算法

prim算法的基本步骤是：假设图的顶点集合为V,边集合为E,初始化集合U={u},此时集合中只有一个结点u,从u的邻接顶点中选取一个顶点v，使得这两个顶点之间的权重最小，然后把v加入结合U中，再从结点v出发，选取最小权重对应的结点加入集合，循环进行直到所有顶点加入集合。

以上图为例，被访问的结点顺序为1 ,3,4,2,5

最小生成树的权重和为11.，最小生成树用红线标出。

prim算法的程序如下：

# include <iostream>
# include <cstdlib>
using namespace std;
const int Max =0x7fffffff;
const int N=50;

int n;
int g[N][N],dis[N],visited[N];

 
int prim()
{
    int i,j;
	int pos,min;
	int ans=0;
    memset(visited,0,sizeof(visited));
    visited[1]=1;pos=1;
    for(i=2;i<=n;i++)
        dis[i]=g[pos][i];
    for(i=1;i<n;i++)
    {
     min=Max;
     for(j=1;j<=n;j++)
         if(visited[j]==0&&min>dis[j])
         {
             min=dis[j];
			 pos=j;
         }
    ans+=min;
    visited[pos]=1;
    for(j=1;j<=n;j++)
        if(visited[j]==0&&dis[j]>g[pos][j])
            dis[j]=g[pos][j];
    }
    return ans;
}
 
int main()
{
    int i=1,j=1;
	int ans=0;
	int w;
	cout<<"输入结点数目："<<endl;
    cin>>n;
	for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
		{
			if(i==j)
				g[i][j]=0;
			else
                g[i][j]=Max;
		}
		cout<<"输入边的数目："<<endl;
		int edgenum;
		cin>>edgenum;
		int v1,v2;
		cout<<"输入结点编号和对应的权值"<<endl;
    for(i=1;i<=edgenum;i++)
        {
            cin>>v1>>v2>>w;
            g[v1][v2]=g[v2][v1]=w;
        }
        ans=prim();
        cout<<ans<<endl;
		system("pause");
    return 0;
}

kruskal算法的基本思想是：先对图中所有边的权重进行排序，然后按照从小到大的顺序，如果这条边的两个顶点不在一个联通分量中，则将这条边加入集合，直到图中所有的顶点都出现在集合中。

也可以这样理解，先把n个顶点看成n棵树，每个数一个结点，每次选取树间的最小边，如果最小边对应的两个顶点不在同一颗树上，那么则合成一颗树，重复n-1步就可以连接n个顶点，得到最小生成树。

kruskan算法的代码是：

#include<iostream>
#include<algorithm>
using namespace std;
struct Edge
{
	int a;
	int b;
	int weight;
}edges[50];
int cmp(const void *a,const void *b)
{
	Edge *p=(Edge *)a;
	Edge *q=(Edge *)b;
	return p->weight-q->weight;
}
int parent[30];
void unionsetset(int root1,int root2)   
{   
	int tmp=parent[root1]+parent[root2];
	if(parent[root1]<=parent[root2])
	{
		parent[root2]=root1;
		parent[root1]=tmp;
	}
	else
	{
		parent[root1]=root2;
		parent[root2]=tmp;
	}
}
int find(int v)
{
	if(parent[v]==-1)
		return v;
	else
		return parent[v]=find(parent[v]);
}
int main()
{       
	    int n;
	    cout<<"输入结点数目:"<<endl;
	    cin>>n;
		int edgenum;
		cout<<"输入边的数目:"<<endl;
		cin>>edgenum;
		int i;
		for(i=0;i<=n;i++)
			parent[i]=-1;
	    int c1,c2;
		for(int i=0;i<edgenum;i++)
		{
			int w;
			cin>>c1>>c2>>w;
			edges[i].a=c1;
			edges[i].b=c2;
			edges[i].weight=w;
		}
		qsort(edges,edgenum,sizeof(Edge),cmp);
		int ans=0;
		int count=1;
		for(int i=0;i<edgenum;i++)
		{
			int root1=find(edges[i].a);
			int root2=find(edges[i].b);
			if(root1!=root2){
			unionsetset(root1,root2);
			ans+=edges[i].weight;
			count++;
			if(count==n) 
				break;
			}
		}
	    cout<<ans<<endl;
		system("pause");
	    return 0;
}