学科分类
目录
数据结构

克鲁斯卡尔(Krushal)算法

Prim算法是以某个顶点为起点,逐条寻找依附于当前顶点的边中权值最小的边来构建最小生成树,在此过程中将用到的顶点依次加入顶点集U中,直到U=V为止,其过程产物为图的一个连通子图。而Kruskal算法是将图的所有边依照权值排序,依次取边,直到边集TE中边的数目为n-1为止,其过程产物为图的多个连通子图。

假设当前有一无向连通网图G=(V,E),它的最小生成树为T=(U,TE)。U是顶点集V的子集,TE是边集E的子集。构造最小生成树的步骤如下:

(1)初始化顶点集U=V,即将图中所有顶点放入顶点集U;初始化边集TE为空,此时相当于图中的每一个顶点都是一个连通子图。

(2)将图中的边按照权值递增顺序依次选取,若该边未使生成树形成环路,则加入边集TE,否则舍弃,依次选取下一条边进行判断,直到边集TE中包含n-1条边为止。

使用Kruskal算法求解最小生成树,需要一个存储边集的数组E[],和记录每个顶点所在连通子图编号的数组vset[]。

数组E[]存储图中所有边的相关信息(顶点u,顶点v,权值w),其中的元素按照权值递增排序。数组vset[]中存储每个顶点所在连通子图的编号,vset[i]表示第i个顶点所在连通子图的编号,用于判断一条边的两个顶点加入生成树中是否会形成环路。构造开始时图中的各个顶点皆不相连,每一个顶点都是一个连通子图,所以vset[]中的元素初始值均不相同。

由此,需要构造边的数据结构定义,其定义如下。

//图中边的数据结构定义
typedef struct
{
    int u;        //起点
    int v;        //终点
    int w;        //权值
}Edge;

以上一节图1中的无向网图G为例,展示使用Kruskal算法构建最小生成树的过程。其过程如下图1所示。

图1 Kruskal算法求解最小生成树过程

根据Kruskal算法求解步骤,在使用Kruskal算法对图G求解最小生成树时,首先初始化顶点集U=V,初始化边集TE=∅。此时每个顶点相当于一个连通子图,让每个顶点的编号作为此时辅助变量vset[]中各个连通子图的编号,则vset[6]={0,1,2,3,4,5}。

假设以邻接矩阵作为图G的存储结构,遍历图G的邻接表,将其边存入数组E[]中,并将E[]中数据按照权值递增排序,则E[10]={(3,5,1),(0,2,2),(2,4,3),(4,5,4),(0,3,5),(2,3,5), (0,1,6), (1,2,6),(2,5,6), (1,4,7)}。依次取E[10]中的边:

取E[0]={3,5,1},其中(3,5)为边,1为边上的权值。边(3,5)的顶点v3和v5在vset[]中对应的连通子图编号分别为3和5,vset[3] vset[5],所以顶点v3和v5不会形成回路,将边(3,5)加入边集数组TE中,并将所有连通子图编号为5的元素数值修改为3:这里只需修改vset[5],使vset[5]=vset[3]。此时TE={(3,5)},vset[6]={0,1,2,3,4,3}。过程产物如图1(a)所示。

取E[1]={0,2,2},其中(0,2)为边,2为边上的权值。边(0,2)的顶点v0和v2在vset[]中对应的连通子图编号分别为0和2,vset[0] vset[2],所以顶点v0和v2不会形成回路,将边(0,2)加入边集数组TE中,并将所有连通子图编号为2的元素数值修改为0:这里只需修改vset[2],使vset[2]=vset[0]。此时TE={(3,5),(0,2)},vset[6]={0,1,0,3,4,3}。过程产物图如图1(b)所示。

其后依次选取E[]中元素E[2]、E[3],并将边(2,4)、(4,5)加入边集TE中。边(2,4)加入TE后,TE={(3,5),(0,2),(2,4)},vset[6]={0,1,0,3,0,3},过程产物图如图7-21(c)所示;边(4,5)加入边集TE后,TE={(3,5),(0,2),(2,4),(4,5)},将所有vset[]值为vset[5],即vset[]中所有值为3的元素的数值修改为0,则vset[6]={0,1,0,0,0,0}。过程产物图如图1(d)所示。

之后按照求解步骤,本该选取E[4]={0,3,5},但是vset[]数组中vset[0]=vset[3]=0,选择边(0,3)会构成回路,所以我们放弃这一条边。选择下一条边E[5]={2,3,5},同样因为vset[2]与vset[3]值相等,会构成回路,所以选择放弃。

继续往后选择E[]中元素E[6]={0,1,6}。此时 vset[0]=0,vset[1]=1,vset[0] vset[1],添加边(0,1)不会构成回路,所以选定此边。添加此边后边集TE={(3,5),(0,2),(2,4),(4,5),(0,1)},vset[6]={0,0,0,0,0,0}。

到这里,边集TE中已有6-1=5条边,最小生成树构造完成,结果如图1(e)所示。

结合以上讲解,下面给出求解最小生成树的Kruskal算法。

//排序算法
void Sort(Edge E[], int e)
{
    int i, j;
    for (i = 0; i < e - 1; i++)
    for (j = 0; j < e - i - 1; j++)
    {
        if (E[j].w>E[j + 1].w)
        {
            Edge tmp = E[j];
            E[j] = E[j + 1];
            E[j + 1] = tmp;
        }
    }
}
//克鲁斯卡尔算法求解最小生成树
void Kruskal_MinTree(MGraph *G)
{
    int i, j, u1, v1, sn1, sn2, k;
    int vset[MAX_VERTEX_NUM];        //存放下标对应的顶点所属的连通子图编号
    Edge E[MAX_EDGE_NUM];            //存放图G中的所有边
    k = 0;
//将图转化为边集数组
    for (i = 0; i < G->n; i++)
    for (j = 0; j < i + 1; j++)
    {
        //遍历邻接矩阵,并将存在的权值存入边集数组E[]
        if (G->edges[i][j] && G->edges[i][j] != INF)
        {
            E[k].u = i;
            E[k].v = j;
            E[k].w = G->edges[i][j];
            k++;
        }
    }
     //排序
    Sort(E, k);                    //排序算法:将边集E中的元素按权值大小升序排列
    for (i = 0; i < G->n; i++)
        vset[i] = i;            //初始化vset[]数组,每个顶点相当于一个连通子图
    k = 1;                        //记录已加入生成树中的边的数目
    j = 0;                        //E中边的下标,从0开始
     //寻找合适的边
    while (k < G->n)
    {
        u1 = E[j].u;
        v1 = E[j].v;
        sn1 = vset[u1];            //分别得到一条边两个顶点所属的集合编号
        sn2 = vset[v1];
        if (sn1 != sn2)
        {
            //两个顶点属于不同集合,该边可以作为最小生成树的一条边
            printf("(%d,%d):%d\n", u1, v1, E[j].w);
            k++;                //边计数加一
            for (i = 0; i < G->n; i++)
            if (vset[i] == sn2)    //统一两个集合的编号
                vset[i] = sn1;
        }
        j++;                    //扫描下一条边
    }
}

Kruskal算法中涉及排序,在后面的章节会详细讲解,此时只需要知道它的作用是将边集数组E[]中的数据按照权值的大小递增排序,它的时间复杂度为O(n2)即可。需要重点掌握的是该算法如何在边集数组中找到合适的边,这一部分算法包含在while循环中。while循环从e条边中寻找n-1条边,最坏情况执行e次,其中的for循环执行n次,因为while循环的时间复杂度为O(n2+e),对于连通无向图,e>(n-1),所以使用克鲁斯卡尔算法构造最小生成树的时间复杂度为O(n2)。

点击此处
隐藏目录