数据结构与算法-最小生成树

一、定义

  1. 连通图的生成树是一个极小的连通子图。
  2. 连通图的生成树含有图中全部的顶点。
  3. 只有足以构成一棵树的n-1条边。

最小生成树：我们把构造连通网的最小代价生成树称为最小生成树。
找连通网的最小生成树经典算法有两种：普里姆算法和克鲁斯卡尔算法。

二、普里姆算法（Prim算法）

算法思路

  1. 定义两个数组：adjvex和lowcost；其中adjvex用来保存相关顶点的下标；lowcost用来保存顶点之间的权值。
  2. 初始化两个数组，从V0开始寻找最小生成树，默认V0是最小生成树上的第一个顶点。
  3. 循环lowcost数组，根据权值（权值最小）找到顶点k。此时表示，V0-Vk最小生成树的第一条边。
  4. 更新lowcost[k]=0表示已经将顶点k加入到生成树中。
  5. 循环所有顶点，找到与顶点k有关系的顶点，并将与k顶点之间的权值与lowcost数组中的权值进行比较，并较小的权值更新lowcost数组。
  6. 更新权值的时候，同步需要更新adjvex中的顶点下标。因为此时遍历的是与k顶点有关系的顶点，所以需要将adjvex对应的下标设置为k。

算法的代码实现

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef struct
{
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

/*9.1 创建邻接矩阵*/
void CreateMGraph(MGraph *G)/* 构件图 */
{
    int i, j;
    
    /* printf("请输入边数和顶点数:"); */
    G->numEdges=15;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=10;
    G->arc[0][5]=11;
    G->arc[1][2]=18;
    G->arc[1][8]=12;
    G->arc[1][6]=16;
    G->arc[2][8]=8;
    G->arc[2][3]=22;
    G->arc[3][8]=21;
    G->arc[3][6]=24;
    G->arc[3][7]=16;
    G->arc[3][4]=20;
    G->arc[4][7]=7;
    G->arc[4][5]=26;
    G->arc[5][6]=17;
    G->arc[6][7]=19;
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

/* Prim算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph G){
    int adjvex[MAXVEX] = {0};//保存相关顶点的下标
    int lowcost[MAXVEX] = {0};//保存顶点之间的权值
    
    //初始化lowcost数组，将v0顶点与之有边的权值存入数组，i从1开始说明已经将V0顶点加入到生成树
    for(int i = 1; i<G.numVertexes; i++){
        lowcost[i] = G.arc[0][i];
    }
    
    int k = 0;
    int sum = 0;
    for(int i = 1; i<G.numVertexes; i++){
        int min = INFINITYC;
        int j = 1;
        while(j < G.numVertexes){
            /*
             1、权值为0表示已经加入到生成树中
             2、找到lowcost数组中的最小权值
             3、将最小权值对应的顶点赋值为k，为后面找到与顶点k有关的边做准备
             */
            if(lowcost[j] != 0 && lowcost[j] < min){
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        
        /* 打印当前顶点边中权值最小的边 */
        printf("(V%d, V%d)=%d\n", adjvex[k], k ,G.arc[adjvex[k]][k]);
        sum+=G.arc[adjvex[k]][k];
        //将最小权值对应的顶点标志为已经加入到生成树，后续就不需要再遍历该顶点了。
        lowcost[k] = 0;
            
        //此时已经找到与V0顶点有边且权值最小的顶点k,遍历与K顶点有边的数组，并用权值更新lowcost数组
        for(j = 1;j <G.numVertexes;j++){
            if(lowcost[j] != 0 && G.arc[k][j]<lowcost[j]){
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
    printf("sum = %d\n",sum);
}

int main(int argc, const char * argv[]) {
    printf("Hello,最小生成树_Prim算法\n");
    
    MGraph G;
    CreateMGraph(&G);
    MiniSpanTree_Prim(G);
    return 0;
}

算法复杂度总结

该算法的算法复杂度为O(n2)。

三、克鲁斯卡尔算法（Kruskal算法）

算法思路

  1. 将邻接矩阵转化成边表数组。
  2. 对边表数组，根据权值大小按照从小到大进行排序。
  3. 遍历所有的边，通过parent数组找到边的连接信息；避免出现闭环问题。
  4. 如果不存在闭环，则加入到最小生成树中并修改parent数组。

算法的代码实现

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */

typedef struct
{
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;

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

/*9.1 创建邻接矩阵*/
void CreateMGraph(MGraph *G)/* 构件图 */{
    int i, j;
    
    /* printf("请输入边数和顶点数:"); */
    G->numEdges=15;
    G->numVertexes=9;
    
    for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
    {
        for ( j = 0; j < G->numVertexes; j++)
        {
            if (i==j)
                G->arc[i][j]=0;
            else
                G->arc[i][j] = G->arc[j][i] = INFINITYC;
        }
    }
    
    G->arc[0][1]=10;
    G->arc[0][5]=11;
    G->arc[1][2]=18;
    G->arc[1][8]=12;
    G->arc[1][6]=16;
    G->arc[2][8]=8;
    G->arc[2][3]=22;
    G->arc[3][8]=21;
    G->arc[3][6]=24;
    G->arc[3][7]=16;
    G->arc[3][4]=20;
    G->arc[4][7]=7;
    G->arc[4][5]=26;
    G->arc[5][6]=17;
    G->arc[6][7]=19;
    
    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = i; j < G->numVertexes; j++)
        {
            G->arc[j][i] =G->arc[i][j];
        }
    }
    
}

/* 交换权值以及头和尾 */
void Swapn(Edge *edges,int i, int j){
    Edge temp = edges[j];
    
    edges[j].begin = edges[i].begin;
    edges[j].end = edges[i].end;
    edges[j].weight = edges[i].weight;
    
    edges[i].begin = temp.begin;
    edges[i].end = temp.end;
    edges[i].weight = temp.weight;
}

/* 对权值进行排序 */
void sort(Edge edges[],MGraph *G){
    for(int i = 0; i<G->numEdges; i++){
        for(int j = i+1; j<G->numEdges; j++){
            if(edges[i].weight > edges[j].weight){
                Swapn(edges, i, j);
            }
        }
    }
    
    printf("边集数组根据权值排序之后的为:\n");
    for (int i = 0; i < G->numEdges; i++)
    {
        printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
    }
}

/* 查找连线顶点的尾部下标 */
//根据顶点f以及parent 数组,可以找到当前顶点的尾部下标; 帮助我们判断2点之间是否存在闭环问题;
int Find(int *parent, int f){
    while(parent[f]){
        f = parent[f];
    }
    return f;
}

/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G){
    Edge edges[MAXEDGE] = {0};
    int parent[MAXEDGE] = {0};
    int sum = 0;
    //构建边表集
    int k = 0;
    for(int i = 0; i <G.numVertexes-1; i++){
        for(int j = i+1; j < G.numVertexes; j++){
            if(G.arc[i][j] < INFINITYC){
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                k++;
            }
        }
    }
    
    //对边表集进行权值由小到大的排序
    sort(edges, &G);
    
    //计算最小生成树
    printf("打印最小生成树：\n");
    
    for (int i = 0; i < G.numEdges; i++){
        //此时，若m=n则形成闭环，根据最小生成树的定义，是不允许出现闭环的，所以当出现闭环的时候应该跳过该顶点
        int m = Find(parent, edges[i].begin);
        int n = Find(parent, edges[i].end);
        if(m!=n){
            parent[m]=n;
            /*打印最小生成树路径*/
            printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
            sum += edges[i].weight;
        }
        
    }
    printf("sum = %d\n",sum);
}

int main(int argc, const char * argv[]) {
    printf("Hello,最小生成树_Kruskal算法\n");
    MGraph G;
    CreateMGraph(&G);
    MiniSpanTree_Kruskal(G);
    return 0;
}

算法复杂度总结

此算法的Find函数由边数e决定，时间复杂度为O(loge)，而Find外面还有一层循环循环e次，所以总的算法复杂度为O(eloge)。

总结

对比两个算法，克鲁斯卡尔主要针对边来展开，边数少时效率会高很多，所以对于稀疏图有很大的优势。
普里姆算法对于稠密图，即边数非常多的情况会好一些。

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,128评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,316评论 3赞 388
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,737评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,283评论 1赞 287
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,384评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,458评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,467评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,251评论 0赞 269
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,688评论 1赞 306
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,980评论 2赞 328
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,155评论 1赞 342
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,818评论 4赞 337
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,492评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,142评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,382评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,020评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,044评论 2赞 352