最近都是图，为了防止几次记不住，先把自己理解的写下来，有问题继续改。先把算法过程记下来：
prime算法：
原始的加权连通图——————D被选作起点，选与之相连的权值最小的边
选与D、A相连权值最小的边——————可选的有B（7）、E（8）、G（11）
————————————————————————重复上述步骤，最小生成树
代码：
用maze[M][M]存两点间的长度，vis[M]判断是否使用此边，dis[M]记录最小生成树的权值。
(代码来自学长发的模板）
#include"iostream"
#include"cstring"
#include"cstdio" #define INF 0x7f7f7f7f
#define MAXN 1005 using namespace std; int n,m;
int maze[MAXN][MAXN];
bool vis[MAXN];
int dis[MAXN]; void prim()
{
int ans = ;
dis[] = ;
for(int i = ;i <= n;i++)
{
int mark = INF;
int minn = INF;
for(int j = ;j <= n;j++)
{
if(!vis[j] && dis[j] < minn)//判断每次选的都是当前情况下的最小权值
{
minn = dis[j];
mark = j;
}
}
vis[mark] = true;
ans += dis[mark];
for(int j = ;j <= n;j++)
{
if(!vis[j] && maze[mark][j] < dis[j]) //选边
{
dis[j] = maze[mark][j];
}
}
}
printf("%d\n",ans);
} int main(void)
{
while(~scanf("%d%d",&n,&m))
{
memset(maze,INF,sizeof(maze));
memset(vis,false,sizeof(vis));
memset(dis,INF,sizeof(dis));
while(m--)
{
int x,y,len;
scanf("%d%d%d",&x,&y,&len);
if(x != y && maze[x][y] > len)//初始化两点间的权值
{
maze[x][y] = len;
maze[y][x] = len;
}
}
prim();
}
return ;
}
——prim
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~·*****************************************************************************************************************`~~~
kruskal算法：
—————————————————————————把边排序，先选定最小的边
——————依次找边——————————————————
————————最小生成树
代码好像有点复杂，要用上并查集，决定结合多方自己补个模板(✿◡‿◡)
struct node
{
int st,en,len;
}e[];
int n,m;
int fa[];
bool cmp(const node &n1,const node&n2)
{
return n1.len<n2.len;
}
int findx(int x)//并查集的find
{
if(fa[x]==x) return fa[x];
else
return fa[x]=findx(fa[x]);
}
int kruskal()
{
int ans=;
for(int i=;i<=n;i++) fa[i]=i;//初始化并查集
for(int i=;i<=m;i++)
scanf("%d%d%d",&e[i].st,&e[i].en,&e[i].len);
sort(e+,e+m+,cmp);
for(int i=;i<=m;i++)
{
int fx=findx(e[i].st),fy=findx(e[i].en);
if(fx!=fy)
{
ans+=
fa[fx]=fy;//最小生成树,已结找到的边有同一个父亲
}
} return ans;
}
void judge()
{
int flag=,term=findx();
for(int i=;i<=n;i++)//判断是否连通
{
if(findx(i)!=term)
{
flag=;
break;
}
}
}
——kruskal
图片来自：
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html