最小树算法

1. 求最小生成树的kruska算法，效率尽量高，尽量多点注释！c++代码

/*
基本算法思想：
为使生成树上总的权值之和达到最小，则应使每一条边上的权值尽可能地小，自然应从权值最小的边选起，直至选出 n-1 条互不构成回路的权值最小边为止。
具体作法如下：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通网的最小生成树。
由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选。

用并查积 和 克鲁是卡尔算法实现查找最短边
利用快排按边递增排列，每次从中选出最短边,同时将最短边的两个顶点并入到集合中
心得：利用并查积 和 kruskal算法结合找最短路径可以使查找的效率更高
加入集合中的边都是构成最小生成树的边，所以每家一次sum 都要加上这两个顶点之间的距离
*/
/*下面的代码输入n个节点，然后输入n*（n-1）/2条边及权值，输出是连通这些边的最小权值*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

struct ed
{
int u; //起始点
int v; //终结点
int w; //权重
};
bool cmp(ed a,ed b)
{
return a.w<b.w; //从小到大排序
}
struct ed edge[100000];
int p[105];

int find(int x) //查找x的父亲
{
while(p[x]!=x)
x=p[x];
return x;
}
int kruskal(int n)
{
int i,count=1,sum=0;
for(i=0;i<=n;i++)
p[i]=i; //并查集初始化，每个节点到父亲是自己
int x,y;
sort(edge,edge+n*(n-1)/2,cmp); //快速排序
for(i=0;count<n;i++)
{
x=find(edge[i].u); //点edge[i].u的父亲是x
y=find(edge[i].v); //点edge[i].v的父亲是y
if(x!=y) //判断是否会路
{
count++; //加上一条边
p[x]=y; //把x和y加入统一个集合
sum+=edge[i].w;
}
}
return sum;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF&&n) //输入n个节点
{
int i;
for(i=0;i<n*(n-1)/2;i++) //输入 n*（n-1）/2条边
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); //表示点edge[i].u和点edge[i].v之间的权重为 edge[i].w
printf("%d\n",kruskal(n));
}
return 0;
}

楼主，这可是本人一个字一个字敲出来点，要给分啊

2. 已知一个无向图如下，分别用普里姆和克鲁斯卡尔算法生成最小生成树（假设以1为起点，试画出构造过程）。

1)普里姆算法思想
从图中任意取出一个顶点， 把它当成棵树，然后从与这棵树相接的边中选取一条最短(权值最小)的边， 并将这条边及其所连接的顶点也并入这棵树中，此时得到了一棵有两个顶点的树。然后从与这棵树相接的边中选取一条最短的边，并将这条边及其所连顶点并入当前树中，得到一棵有3个顶点的树。以此类推，直到图中所有顶点都被并入树中为止，此时得到的生成树就是最小生成树。
2)克鲁斯卡尔算法思想
先将边中的权值从小到大排序，每次找出候选边中权值最小的边，就将该边并入生成树中。重复此过程直到所有边都被检测完为止。其中要注意的是克鲁斯卡尔算法需要用到并查集，以此来判断接下来要并入的边是否会和已并入的边构成回路。这两个图分别用普里姆和克鲁斯卡尔生成的最小生成树见图。

需要注意的是，在接下来要并入的最小权值不唯一的情况下，可以选取的边是不唯一的，所以其最小生成树也不唯一。(纯手打，望采纳，谢谢。)

3. 最小生成树 普里姆算法有问

普里姆算法构造最小生成树算法的思想是：选择一个结点，然后从这个结点开始，选择权值最小的边，用一条边连接，然后再以前面的那个结点开始，和你连接的那个结点作为根节点，再选择权值最小的边进行连接。
对权值给出解释：以上图为例，权值就是你第一个图那几条边（弧）上，所标的数字。
对楼主所提出的问题：并不是连接那圆圈中最小的圆圈，如果没错的话，那圆圈中的数字表示的是V1---V6六个顶点，并不是代表数字，以3和6为顶点，找权值最小边，显然6——4为最小，即权值为2，顶点364相连接的时候各以364为顶点寻找最小边，应该先从6连接到2，那么现在加入顶点的为3642顶点，现在以3642为顶点寻找最小边，应该从2连接到1，现在被连接的有63421，在以63421为顶点寻找最小边
出现了问题：如果以5为权值的话，无论从2连接到4还是从3连接到4都出现了环，当然我们知道数中是不能出现环的，所以寻找次小的，剩余5与13之间权值最小为13.所以将1连接5，即得到最小生成树。
楼主可以按照我说的在纸上画一下试试
从6连接到3因为有前提条件：从顶点V3开始用普里姆方法求其最小生成数，可见是从顶点3连接到6，而不是从6连接到3
希望可以解决楼主的疑惑，谢谢！