Prim简单证明：

（1）假设Prim算法得到树G，而最小生成树是T

（2）设在生成G的过程中第一次产生的不在T中的边是e，

（3）在G中去掉e得到的两个连通分支记为V1和V2，那么e连接了V1和V2
（4）把e加入T之后会出现环，在这个环里面肯定有另一条边 f 连接V1,V2（否则T本身就不连通了）。

（5）由Prim算法的贪心策略可知e比f权重低，那么在T里面把f换成e可得一个总权重更小的生成树，与T的最小性矛盾。

模版（邻接矩阵) 复杂度O(V^2) ：

//返回最小生成树权值，返回-1表示不连通 
const int INF=0x3f3f3f3f;
const int MAXN=105;
int dis[MAXN];
bool vis[MAXN];
int prim(int cost[][MAXN],int n)//顶点从1开始，1~n 
{
	int ans=0; 
	for(int i=1;i<=n;i++) dis[i]=cost[1][i];
	for(int i=1;i<=n;i++) vis[i]=false;
	vis[1]=true;
	for(int i=1;i<n;i++) //找的次数n-1次 
	{
		int minn=INF;
		int p=-1;
		for(int j=1;j<=n;j++)
		{
			if(!vis[j]&&dis[j]<minn)
			{
				minn=dis[j]; //找到当前子树最小的边. 
				p=j;
			}
		}
		if(minn==INF) return -1; //不连通。 
		ans=ans+minn;
		vis[p]=true;
		for(int j=1;j<=n;j++)
			if(!vis[j]&& cost[p][j]<dis[j])//更新最小的边 
				dis[j]=cost[p][j];
	}
	return ans;
}

Kruskal简单证明：
（1）假定Kruskal算法中的第k步首次出现错误，算法选了E1，但实际上最小生成树T里没有E1。
（2）那么E1连接了两个连通分支，这两个连通分支在最终的T里是连通的，所以把T和E1放在一起之后形成的图有一个环。在这个环里除了E1，还有一条肯定不在第k步之前出现的边（因为按照定义如果没有的话仅凭前k-1条边和E1不会构成环），依照E1的定义，这个环里存在比E1长的边，用E1换掉这条边之后得到的树T1比T更短，矛盾。

模版 复杂度ElogV：
 

const int MAXN=105;//最大顶点数
const int MAXM=10025;//最大边数
int pre[MAXN]; 
struct Edge{
	int u,v,w;
}edge[MAXM];
bool cmp(Edge a,Edge b)
{//排序规则，权值从小到大 
	return a.w<b.w;
}
int Find(int x)
{
return pre[x] == x ? x : pre[x] = Find(pre[x]);
} 
int Kruskal(int n,int m)//传入顶点数,边数 
{//开始独立集合为n个，生成最小生成树时集合为1. 
	int cnt=n; 
	int ans=0;
	for(int i=1;i<=n;i++) pre[i]=i; 
	sort(edge,edge+m,cmp);
	for(int i=0;i<m;i++)
	{
		int t1=Find(edge[i].u);
		int t2=Find(edge[i].v);
		if(t1!=t2)
		{
			pre[t2]=t1;
			ans=ans+edge[i].w;
			cnt--;
		}
		if(cnt==1)break;
	} 
	if(cnt>1) return -1;//不连通
	return ans; 
}

练习：http://acm.hdu.edu.cn/showproblem.php?pid=1233

prim:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);
const int INF=0x3f3f3f3f;
const int MAXN=105;
int dis[MAXN];
bool vis[MAXN];
int prim(int cost[][MAXN],int n)//顶点从1开始，1~n
{
    int ans=0;
    for(int i=1;i<=n;i++) dis[i]=cost[1][i];
    for(int i=1;i<=n;i++) vis[i]=false;
    vis[1]=true;
    for(int i=1;i<n;i++) //找的次数n-1次
    {
        int minn=INF;
        int p=-1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&dis[j]<minn)
            {
                minn=dis[j]; //找到当前子树最小的边.
                p=j;
            }
        }
        if(minn==INF) return -1; //不连通。
        ans=ans+minn;
        vis[p]=true;
        for(int j=1;j<=n;j++)
            if(!vis[j]&& cost[p][j]<dis[j])//更新最小的边
                dis[j]=cost[p][j];
    }
    return ans;
}
int main()
{
    int n;
    int cost[MAXN][MAXN];
    IOS;while(cin>>n&&n)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            cost[i][j]=INF;
            int m=n*(n-1)/2;
            for(int i=1;i<=m;i++)
            {
                int x,y,z;
               cin>>x>>y>>z;
                cost[x][y]=cost[y][x]=z;
            }
            cout<<prim(cost,n)<<endl;
    }
    return 0;
}

Kruskal:

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=105;//最大顶点数
const int MAXM=10025;//最大边数
int pre[MAXN]; 
struct Edge{
	int u,v,w;
}edge[MAXM];
bool cmp(Edge a,Edge b)
{//排序规则，权值从小到大 
	return a.w<b.w;
} 
int Find(int x)
{
	return pre[x]==x?x:x=Find(pre[x]);
} 
int Kruskal(int n,int m)//传入顶点数,边数 
{//开始独立集合为n个，生成最小生成树时集合为1. 
	int cnt=n; 
	int ans=0;// 
	for(int i=1;i<=n;i++) pre[i]=i; 
	sort(edge,edge+m,cmp);
	for(int i=0;i<m;i++)
	{
		int t1=Find(edge[i].u);
		int t2=Find(edge[i].v);
		if(t1!=t2)
		{
			pre[t2]=t1;
			ans=ans+edge[i].w;
			cnt--;
		}
		if(cnt==1)break;
	} 
	if(cnt>1) return -1;//不连通
	return ans; 
}
int main()
{
	int n;
	 IOS;while(cin>>n&&n)
	{
		int m=n*(n-1)/2;
		for(int i=0;i<m;i++)
		cin>>edge[i].u>>edge[i].v>>edge[i].w;
		cout<<Kruskal(n,m)<<endl;
	}
	return 0;
}

由于笔者能力有限，如果有任何问题请及时联系我，留言或者qq：2531649293