kruskal克鲁斯卡尔算法

给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树.

求最小生成树的算法
(1) 克鲁斯卡尔算法
图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的.该方法对于边相对比较多的不是很实用,浪费时间.

方法:将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树,(n为顶点数)就是一个贪心算法；

Kruskal适合一维数组来管理数据 ;
 
第一步:由边集数组选第一条边

第二步:选第二条边,即权值为2的边

第三步:选第三条边,即权值为3的边

第四步:选第四条边,即权值为4的边

第五步:选第五条边

/*
 * Introduction to Algorithms
 * Chapter 23 --- MST.Kruskal
 * Tanky Woo @ www.WuTianQi.com
 * 2012.1.7
 */

#include <iostream>
#include <algorithm>
using namespace std;

const int maxint = 999999;

typedef struct Road{
    int c1, c2;   // a到b
    int value;  // 权值
}Road;

int no;
int line;//记录实际关系数
Road road[100];//设一个比较大的值，实际看输入最小生成树中：边数e=n-1
int node[101];//最小生成树：n顶点数

bool myCmp(const Road &a, const Road &b)
{
    if(a.value < b.value)
        return 1;
    return 0;
}

//node[2]=1 node[8]=1 ,node[3]=1,共同的祖先,如果(3,8)加进去，则构成回路，不要
//有点像并查集
int Find_Set(int n)
{
    if(node[n] == -1)
        return n;
    return node[n] = Find_Set(node[n]);
}

bool Merge(int s1, int s2)
{
    int r1 = Find_Set(s1);
    int r2 = Find_Set(s2);
    if(r1 == r2)//如果相等证明构成回路，则直接返回一个0,不要把顶点加进来(下一步是加进去的)
        return 0;
    if(r1 < r2)
        node[r2] = r1;
    else
        node[r1] = r2;
    return 1;
}

int main()
{
    freopen("input.txt", "r", stdin);
    //初始化全为-1
    memset(node, -1, sizeof(node));
    scanf("%d",&no);
    scanf("%d",&line);
    int i;
    for(i=0; i<line; ++i)
    {
        cin >> road[i].c1 >> road[i].c2 >> road[i].value;
    }
    sort(road, road+line, myCmp);
    int sum = 0, count = 0;  // sum是MST的值，count是记录已使用的点数
    for(i=0; i<line; ++i)
    {
        if(Merge(road[i].c1, road[i].c2))//如果返回的为0,则证明构成回路，不要加进
        {
            count ++;
            sum += road[i].value;
        }
        if(count == no-1)//e=n-1已经连通，可以退出
            break;
    }
    cout << sum << endl;
    return 0;
}


/*
input.txt:
9
14
1 2 4
1 8 8
2 3 8
2 8 11
3 4 7
3 6 4
3 9 2
4 5 9
4 6 14
5 6 10
6 7 2
7 8 1
7 9 6
8 9 7
*/