算法竞赛中常用的算法，求图的最小生成树
过程：
对边集排序，
选取最小边，将连接的节点放到一个集合中
选取次小的边，当边连接的定点不在同一个集合中时，合并集合。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int u[200],v[200];//最大有200条边，每条边的两个节点的位置
float w[200];//每条边的权值
int f[200];//200个边的父节点，并查集使用
int node_num,side_num;//节点个数，边的个数
int r[200];//储存排序后，第小的边的编号
queue<int> side;
void build_map()//建立图
{
    int i;
    i = 0;
    printf("输入节点个数：\n");
    scanf("%d", &node_num);//输入节点个数
    printf("输入边的信息：节点1，节点2，权重 \n");
    while(1)
    {
        int a, b;
        float c;
        if (scanf("%d,%d,%f", &a, &b, &c) != 3) break;//输入该边的两个定点以及该边的权重
        u[i] = a;
        v[i] = b;
        w[i] = c;
        i++;
    }
    side_num = i;//统计边的个数
}
int cmp(int i, int j)
{
    return w[i] < w[j];
}
int find(int x)
//并查集，用于判断是否在同一个集合
//这是这些天遇到的第二个暴力，简洁，优美的算法了
{
    return f[x] == x ? x : find(f[x]);
}
int main()
{
    build_map();
    for (int i = 0; i < node_num; i++)
    {
        f[i] = i;//初始化并查集
    }
    for (int i = 0; i < side_num; i++)
    {
        r[i] = i;//初始化边的编号
    }
    sort(r, r + side_num, cmp);//对边按照顺序排列
    for (int i = 0; i < side_num; i++)
    {
        int k = r[i];
        int x = find(u[k]);
        int y = find(v[k]);
        if (x != y)//若两个节点不在同一个集合里，则合并
        {
            f[x] = y;
            side.push(r[i]);
        }
    }
    printf("边集为：\n");
    while (!side.empty())//输出边集
    {
        int m = side.front();
        side.pop();
        printf("%d,%d\n", u[m], v[m]);
    }
    return 0;
}

阅读更多

更多精彩内容