最小生成树问题-kruskal算法

本文主要是介绍最小生成树问题-kruskal算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

kruskal适合稀疏图

定义边结构体

typedef struct
{
    int begin;
    int end;
    int weight;
}Edge;

算法实现代码

//邻接矩阵转边集数组
void MGraph2EdgeArr(MGraph G, Edge* edge);
//找到顶点index的根节点下标返回
int Find(int* parent, int index);
//使用克鲁斯卡尔算法进行最小生成树的创建
void MiniSpanTree_Kruskal(MGraph G);
//邻接矩阵转编辑数组，按照权值排序，由小到大
void MGraph2EdgeArr(MGraph G, Edge* edge)
{
    int i, j,k=0;
    Edge temp;
    int min;
    for (i = 0; i < G.numVertexes;i++)
    {
        for (j = i + 1; j < G.numVertexes;j++)
        {
            if (G.arc[i][j]!=INFINITY)    //有边
            {
                edge[k].begin = i;
                edge[k].end = j;
                edge[k].weight = G.arc[i][j];
                k++;
            }
        }
    }

    //按照冒泡大小进行排序
    for (i = 0; i < k;i++)
    {
        for (j = i; j < k;j++)
        {
            if (edge[j].weight<edge[i].weight)
            {
                temp = edge[i];
                edge[i] = edge[j];
                edge[j] = temp;
            }
        }
    }
}
int Find(int* parent, int f)
{
    while (parent[f] > 0)
        f = parent[f];
    return f;
}
void MiniSpanTree_Kruskal(MGraph G)
{
    Edge edges[MAXVEX];    //定义边集数组
    int parent[MAXVEX];    //定义生成树的父节点，也可以使用结构体，但是更加浪费空间
    int i,n,m;
    MGraph2EdgeArr(G, edges);    //邻接矩阵转边集数组

    //开始进行初始化
    for (i = 0; i < MAXVEX; i++)
        parent[i] = 0;    //这里是0代表根节点，我们也可以使用-1，正负无穷等
    //进行合并操作
    for (i = 0; i < G.numEdges;i++)
    {
        n = Find(parent, edges[i].begin);    //找到顶点edges[i].begin的根节点下标
        m = Find(parent, edges[i].end);        //找到顶点edges[i].end的根节点位置
        if (n!=m)    //若是根节点下标不是一样的，就说不在一棵树上，不会形成环，我们放心合并
        {
            parent[n] = m;    //将n树合并到m树，表示该边被放入生成树
        }
    }
}

这篇关于最小生成树问题-kruskal算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！