数据结构(五)图---最小生成树(克鲁斯卡尔算法)

时间:2022-06-05 12:57:16

一:回顾普里姆算法

数据结构(五)图---最小生成树(普里姆算法)

普里姆算法是以某个顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树。是临时决定路径。
例如:我们参观某个展会,从一个入口进入,然后我们会选择最感兴趣的场馆进入观看,看完后再用同样的方法看下一个。

二:克鲁斯卡尔算法(稀疏图)

推文:https://www.cnblogs.com/qianbixin/p/5005161.html(转载自)

例如上面参观,我们为何不先决定去看那些展馆,事先计划好,然后进园后直接按照所决定的路径进行观看。这就是克鲁斯卡尔算法的思想

注意:

克鲁斯卡尔算法需要我们了解生成树的概念,我们可以回到普里姆算法回顾下

(一)基本思想

1)构造一个只含n个顶点,边集为空的子图。若将图中各个顶点看成一棵树的根节点,则它是一个含有n棵树的森林。
(2)从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图。也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之
(3)依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。

或者

(1)将图中的所有边都去掉。
(2)将边按权值从小到大的顺序添加到图中,保证添加的过程中不会形成环
(3)重复上一步直到连接所有顶点,此时就生成了最小生成树。这是一种贪心策略。

(二)难点

判断某条边<u, v>的加入是否会在已经选定的边集集合中形成环。

(三)解决思路

使用并查集,分别找出两个顶点u, v所在树的根节点。若根节点相同,说明u, v在同一棵树中,则u, v连接起来会形成环;若根节点不同,则u, v不在一棵树中,连接起来不会形成环,而是将两棵树合并。

推文:数据结构(四)树---集合的表示及查找(并查集)

(四)图解过程

数据结构(五)图---最小生成树(克鲁斯卡尔算法)         数据结构(五)图---最小生成树(克鲁斯卡尔算法)

数据结构(五)图---最小生成树(克鲁斯卡尔算法)         数据结构(五)图---最小生成树(克鲁斯卡尔算法)

三:代码实现

数据结构定义

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAXVEX 100    //最大顶点数
#define INFINITY 65535    //用0表示∞

typedef char VertexType;    //顶点类型,字符型A,B,C,D...
typedef int EdgeType;    //边上权值类型10,15,...

//邻接矩阵结构
typedef struct
{
    VertexType vers[MAXVEX];    //顶点表
    EdgeType arc[MAXVEX][MAXVEX];    //邻接矩阵,可看作边表
    int numVertexes, numEdges;    //图中当前的顶点数和边数
}MGraph;


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

函数定义

//创建邻接矩阵
void CreateMGraph(MGraph* G);
//邻接矩阵转边集数组
void MGraph2EdgeArr(MGraph G, Edge* edge);
//显示邻接矩阵
void showGraph(MGraph G);
//找到顶点index的根节点下标返回
int Find(int* parent, int index);
//使用克鲁斯卡尔算法进行最小生成树的创建
void MiniSpanTree_Kruskal(MGraph G);

创建邻接矩阵

数据结构(五)图---最小生成树(克鲁斯卡尔算法)数据结构(五)图---最小生成树(克鲁斯卡尔算法)
void CreateMGraph(MGraph* G)
{
    int i, j, k, w;
    G->numVertexes = 9;
    G->numEdges = 15;
    //读入顶点信息
    G->vers[0] = 'A';
    G->vers[1] = 'B';
    G->vers[2] = 'C';
    G->vers[3] = 'D';
    G->vers[4] = 'E';
    G->vers[5] = 'F';
    G->vers[6] = 'G';
    G->vers[7] = 'H';
    G->vers[8] = 'I';

    //getchar();    //可以获取回车符
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j < G->numVertexes; j++)
            G->arc[i][j] = INFINITY;    //邻接矩阵初始化

    G->arc[0][1] = 10;
    G->arc[0][5] = 11;
    G->arc[1][2] = 18;
    G->arc[1][6] = 16;
    G->arc[1][8] = 12;
    G->arc[2][3] = 22;
    G->arc[2][8] = 8;
    G->arc[3][4] = 20;
    G->arc[3][7] = 16;
    G->arc[3][6] = 24;
    G->arc[3][8] = 21;
    G->arc[4][5] = 26;
    G->arc[4][7] = 7;
    G->arc[5][6] = 17;
    G->arc[6][7] = 19;

    for (k = 0; k < G->numVertexes; k++)    //读入numEdges条边,建立邻接矩阵
    {
        for (i = k; i < G->numVertexes; i++)
        {
            G->arc[i][k] = G->arc[k][i];    //因为是无向图,所有是对称矩阵
        }
    }
}
CreateMGraph创建邻接矩阵

邻接矩阵转边集数组

//邻接矩阵转编辑数组,按照权值排序,由小到大
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;
            }
        }
    }
}

并查集操作,获取一个顶点f的根节点下标,这里没有使用结构体,而是将数组下标作为了数据,节省了不必要空间

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树,表示该边被放入生成树
            printf("(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}

全部代码

数据结构(五)图---最小生成树(克鲁斯卡尔算法)数据结构(五)图---最小生成树(克鲁斯卡尔算法)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAXVEX 100    //最大顶点数
#define INFINITY 65535    //用0表示∞

typedef char VertexType;    //顶点类型,字符型A,B,C,D...
typedef int EdgeType;    //边上权值类型10,15,...

//邻接矩阵结构
typedef struct
{
    VertexType vers[MAXVEX];    //顶点表
    EdgeType arc[MAXVEX][MAXVEX];    //邻接矩阵,可看作边表
    int numVertexes, numEdges;    //图中当前的顶点数和边数
}MGraph;


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

//创建邻接矩阵
void CreateMGraph(MGraph* G);
//邻接矩阵转边集数组
void MGraph2EdgeArr(MGraph G, Edge* edge);
//显示邻接矩阵
void showGraph(MGraph G);
//找到顶点index的根节点下标返回
int Find(int* parent, int index);
//使用克鲁斯卡尔算法进行最小生成树的创建
void MiniSpanTree_Kruskal(MGraph G);


int main()
{
    MGraph MG;
    CreateMGraph(&MG);
    showGraph(MG);
    MiniSpanTree_Kruskal(MG);
    system("pause");
    return 0;
}

//生成邻接矩阵
void CreateMGraph(MGraph* G)
{
    int i, j, k, w;
    G->numVertexes = 9;
    G->numEdges = 15;
    //读入顶点信息
    G->vers[0] = 'A';
    G->vers[1] = 'B';
    G->vers[2] = 'C';
    G->vers[3] = 'D';
    G->vers[4] = 'E';
    G->vers[5] = 'F';
    G->vers[6] = 'G';
    G->vers[7] = 'H';
    G->vers[8] = 'I';

    //getchar();    //可以获取回车符
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j < G->numVertexes; j++)
            G->arc[i][j] = INFINITY;    //邻接矩阵初始化

    G->arc[0][1] = 10;
    G->arc[0][5] = 11;
    G->arc[1][2] = 18;
    G->arc[1][6] = 16;
    G->arc[1][8] = 12;
    G->arc[2][3] = 22;
    G->arc[2][8] = 8;
    G->arc[3][4] = 20;
    G->arc[3][7] = 16;
    G->arc[3][6] = 24;
    G->arc[3][8] = 21;
    G->arc[4][5] = 26;
    G->arc[4][7] = 7;
    G->arc[5][6] = 17;
    G->arc[6][7] = 19;

    for (k = 0; k < G->numVertexes; k++)    //读入numEdges条边,建立邻接矩阵
    {
        for (i = k; i < G->numVertexes; i++)
        {
            G->arc[i][k] = G->arc[k][i];    //因为是无向图,所有是对称矩阵
        }
    }
}

//邻接矩阵转编辑数组,按照权值排序,由小到大
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;
            }
        }
    }
}

//显示邻接矩阵
void showGraph(MGraph G)
{
    for (int i = 0; i < G.numVertexes; i++)
    {
        for (int j = 0; j < G.numVertexes; j++)
        {
            if (G.arc[i][j] != INFINITY)
                printf("%5d", G.arc[i][j]);
            else
                printf("    0");
        }
        printf("\n");
    }
}

//并查集操作,获取一个顶点f的根节点下标
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树,表示该边被放入生成树
            printf("(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}
View Code

数据结构(五)图---最小生成树(克鲁斯卡尔算法)

四:总结

将图中各边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边, 若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n为顶点数)
克鲁斯卡尔算法的时间复杂度为O(eloge)跟边的数目有关,适合稀疏图。(若图的顶点数为n,边数为e)。