最小生成树，克鲁斯卡尔（Kruskal）算法，邻接表

基本思想： 将所有顶点之间路径权值，从小到大有序排列，并在程序中优先遍历路径小的顶点，记录不存在环的路径，直至全部循环完毕。 关键： 1、将输入的边的顺序按边的权值从小到大排序。 2、在遍历的过程中判断是否生成环（难点）。 样例： 这里我用123456来代替ABCDEF

样例输入：

6 10

1 2 6
1 3 1
1 4 5
2 3 5
3 4 5
2 5 3
3 5 6
3 6 4
4 6 2
5 6 6

样例输出：

依次连接的边：
1 3 1
4 6 2
2 5 3
3 6 4
2 3 5
总权值：15

代码实现：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct edge
{
    int s,e,w;
};
bool operator < (const edge &a,const edge &b)
{
    return a.w<b.w;
}
int Find(int *p,int f)
{
    while(p[f]>0)
        f=p[f];
    return f;
}
int main()
{
    cout<<"输入顶点和边的个数："<<endl;
    int n,m;
    cin>>n>>m;
    cout<<"输入起点、终点和权值"<<endl;
    edge a[1000];
    int i,d,t;
    for(i=0;i<m;i++)
    {
        cin>>a[i].s>>a[i].e>>a[i].w;
    }
    sort(a,a+m);
    int b[1000];     //存放最小生成树的顶点
    int sum=0;
    memset(b,0,sizeof(b));
    cout<<"依次连接的边："<<endl;
    for(i=0;i<m;i++)
    {
        d=Find(b,a[i].s);
        t=Find(b,a[i].e);
        if(d!=t)         //d==t代表会形成环
        {
            sum+=a[i].w;
            b[d]=t;
            cout<<a[i].s<<" "<<a[i].e<<" "<<a[i].w<<endl;
        }
    }
    cout<<"总权值："<<sum<<endl;
    return 0;
}