1/一棵树的任意两个节点都有路径
2/任何两个顶点之间都有边（弧）相连称为完全图
完全图有n个节点时，总共有n*(n-1)/2条边
3/生成树只能有n-1条边
prim的实现：
起始点start
u=start;
do{
将u的所有相连的边储存到一个最小堆中
while（堆非空）
利用最小堆性质弹出最小权值的边(这些边的起始点u一定visited)
此边的顶点分别是u和v
判断点v是否visited
若是则重新在堆中查找
若否则将该边保存至MST中，break结束；
}while（MST中边数达到N-1）
prim的实现2：//严蔚敏数据结构：
MST中的点集为U
主要思想是每次都从V-U到U的边中找到权值最小的边
找到该边时将该边在V-U中的顶点转移到U中
具体实现是：
利用一个closedge[]数组，closedge[i].lowcost表示V-U中的点i到U的最小权值
如果只是求最小生成树的权值和的话，直接创建lowcost[]数组更好
lowcost[]数组实际上运用了一个窍门
若点v到u0的lowcost[v]=1
当u1加入U之后
若v到u1有边，且权值比lowcost[v]小
则lowcost[v]=w(u1,v)
总之，lowcost[]总能找到U到V-U中最小权值的边
将V-U中的点移至U中的方法是利用visited[]数组标记，visited[U]=1,visited[V-U]=0
U==V时，辅助变量cnt==n
while(U!=V){
for
U中的点u
for V-U中的点v
若(u,v)的权值w(u,v)小于closedge[v].lowcost)
closedge[v].lowcost=w(u,v)
若w(u,v)<min
min=w(u,v)
}
kruskal的实现：
将所有边都放进最小堆中
while(MST中边数为N-1)
从最小堆中弹出最小权值边
该边的两个顶点u,v，可利用并查集找出u与v的根
若u的根与v的根相同，则说明u与v在同一连通分量中，此时，添加此边会在MST中形成环，故将该边舍弃
若不同，则将此边加入MST中
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1233
贴上Prim代码：
#include<iostream> #include<cstring> #include<cmath> #define INF 9999999 using namespace std; int graph[100][100]; int lowcost[100]; int n; bool vis[100]; int Min,sum,cur; int prim(){ cur=1; sum=0; vis[1]=1; for(int cnt=1;cnt<n;cnt++){ //n-1′? for(int i=1;i<=n;i++) if(!vis[i] && graph[cur][i]<lowcost[i]) lowcost[i]=graph[cur][i]; Min=INF; for(int i=1;i<=n;i++) { if(!vis[i] && lowcost[i]<Min){ Min=lowcost[i]; cur=i; } } vis[cur]=1; sum+=Min; } return sum; } int main (){ while(cin>>n){ if(!n) break; int u,v,w; memset(graph,INF,sizeof(graph)); memset(vis,0,sizeof(vis)); memset(lowcost,INF,sizeof(lowcost)); for(int i=0;i<n*(n-1)/2;i++){ cin>>u>>v>>w; graph[u][v]=w; graph[v][u]=w; } cout<prim()<<endl; } return 0; }
贴上Kruskal代码
//并查集的实现 #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn=100; int parent[maxn]; int Rank[maxn]; int n;//集元素的个数 struct edgenode{ int u,v,w; }; int find(int x){ while(parent[x]!=x) x=parent[x]; return x; } void Union(int x,int y){ //x=find(x); //y=find(y); if(Rank[x]==Rank[y]) //同秩的时候，令y成为x的父节点 { Rank[y]++; parent[x]=y; } else if(Rank[x]>Rank[y]) parent[y]=x; else parent[x]=y; } //加权规则 void makeSet(){ for(int i=1;i<=n;i++) { Rank[i]=0; parent[i]=i; } } bool cmp (edgenode& ed1,edgenode& ed2) { return ed1.w<ed2.w; } edgenode edge[maxn*maxn/2]; int sum; int x,y,k; int kruskal(){ sum=0; sort(edge,edge+k,cmp); for(int i=0;i<k;i++){ x=find(edge[i].u); y=find(edge[i].v); if(x!=y){ parent[x]=y; sum+=edge[i].w; } } return sum; } int main (){ while(cin>>n&&n) { k=n*(n-1)/2; //边数k for(int i=0;i<k;i++) cin>>edge[i].u>>edge[i].v>>edge[i].w; makeSet(); cout<<kruskal()<<endl; } return 0; }