数算---最小生成树

前言

上篇文章介绍了图的相关基本概念，本篇我们将继续探索图的应用。

基本概念

连通图的生成树：所谓一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只足以构成一棵树的n-1条边。
条件如下：

  1. 图是连通图。
  2. 图中包含了n个顶点。
  3. 图中边的数量等于n-1条边。
生成树

上图中图1中有8个顶点和9条边，图2中有8个顶点7条边，均满足连通的条件，但是图1不满足n-1条边的条件，则不是连通图的生成树。图2则全满足生成树的所有条件。

面试题

上面连通图的生成树问题中，只需满足上方三个条件即可，但如果给每条边添加上权值，找出权值和最小的生成树那就相对更复杂了。
下面是阿里的一道数据结构与算法题，假设目前N个顶点，每个顶点连接的路径不一样，请你设计一个算法，快速找出能覆盖所有顶点的最小成本的路径。（类似于一个村庄的网络布局，在成本最小的情况下全村通网）

那么就引出了最小生成树的概念！
最小生成树：把构成连通网的最小代价的生成树称为最小生成树。

普里姆[Prim]算法

思路：

  1. 定义两个数组：adjvex数组用来保存相关顶点的下标，lowcost保存顶点之间的权值。
  2. 初始化2个数组，从v0开始寻找最小生成树，默认v0时最小生成树上第一个顶点。即lowcost数组默认为邻接矩阵第一行数据。
  3. 循环lowcost数组，根据权值大小，找到最小的权值对应的下标k，即顶点k。
  4. 更新lowcost数组。

  5. 比较顶点k相连的顶点权值与lowcost数组中相应位置权值大小，取较小值。已经存入最小生成树的则不用管。


    邻接矩阵

执行过程：

  1. 比较lowcost数组中权重值，由于默认V0已经加入最小生成树，则lowcost[0] = 0；10、11 分别为V0与V1、V5链接的权值，10更小，则此时k = 1。


    第一次执行

  2. lowcost[1] = 0，表示V1加入最小树，将与V1相连的顶点对应的权值放进lowcost数组中，接着比较数组中权值大小，此时为11，则k = 5，将与V5连接的顶点权值与lowcost数组相应位置比较，小了的就替换，大了就不变，发现有V4、V6与V5相连，V5-V6权值17大于lowcost[6] = 16，则保持16不变，V5-V4权值26小于lowcost[4]最大值，则替换lowcost[4] = 26.


    第二次执行

  3. 接着找出lowcost数组中最小权值12，此时k = 8，lowcost[8] = 0，表示V8添加到最小树中，与V8相连的顶点有V1、V2、V3，V1已经添加进最小树，则只需关注V2、V3，比较相应的权值。


    第三次执行

  4. 依照如上方式依次执行得到如下最终结果：


    最终结果

    最终所有顶点都加入到最小树中。最小路径则为下图中所有黑色粗线连线。


    最小生成树

代码实现

#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 min, i, j, k;
    int sum = 0;
    /* 保存相关顶点下标 */
    int adjvex[MAXVEX];
    /* 保存相关顶点间边的权值 */
    int lowcost[MAXVEX];
    
    /* 初始化第一个权值为0，即v0加入生成树 */
    /* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */
    lowcost[0] = 0;
    
    /* 初始化第一个顶点下标为0 */
    adjvex[0] = 0;
    
    //1. 初始化
    for(i = 1; i < G.numVertexes; i++)    /* 循环除下标为0外的全部顶点 */
    {
        lowcost[i] = G.arc[0][i];    /* 将v0顶点与之有边的权值存入数组 */
        adjvex[i] = 0;                    /* 初始化都为v0的下标 */
    }
    
    //2. 循环除了下标为0以外的全部顶点, 找到lowcost数组中最小的顶点k
    for(i = 1; i < G.numVertexes; i++)
    {
        /* 初始化最小权值为∞， */
        /* 通常设置为不可能的大数字如32767、65535等 */
        min = INFINITYC;
        
        j = 1;k = 0;
        while(j < G.numVertexes)    /* 循环全部顶点 */
        {
            /* 如果权值不为0且权值小于min */
            if(lowcost[j]!=0 && lowcost[j] < min)
            {
                /* 则让当前权值成为最小值,更新min */
                min = lowcost[j];
                /* 将当前最小值的下标存入k */
                k = j;
            }
            j++;
        }
        
        /* 打印当前顶点边中权值最小的边 */
        printf("(V%d, V%d)=%d\n", adjvex[k], k ,G.arc[adjvex[k]][k]);
        sum+=G.arc[adjvex[k]][k];
        
        /* 3.将当前顶点的权值设置为0,表示此顶点已经完成任务 */
        lowcost[k] = 0;
        
        /* 循环所有顶点,找到与顶点k 相连接的顶点
         1. 与顶点k 之间连接;
         2. 该结点没有被加入到生成树;
         3. 顶点k 与 顶点j 之间的权值 < 顶点j 与其他顶点的权值,则更新lowcost 数组;
         
         */
        for(j = 1; j < G.numVertexes; j++)
        {
            /* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
            if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
            {
                /* 将较小的权值存入lowcost相应位置 */
                lowcost[j] = G.arc[k][j];
                /* 将下标为k的顶点存入adjvex */
                adjvex[j] = k;
            }
        }
    }
    printf("sum = %d\n",sum);
}

int main(void)
{
    printf("Hello,最小生成树_Prim算法\n");
    
    MGraph G;
    CreateMGraph(&G);
    MiniSpanTree_Prim(G);
    
    return 0;
    
}
克鲁斯卡尔[Kruskal]算法

思路：

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

执行过程：

边表数组

  1. begin = 4, end = 7, weight = 7 ，parent[4] = 0, n = 4, parent[7] = 0, m = 7, n != m ,所以此时parent[4] = 7。


  2. begin = 2, end = 8, weight = 8,n = 2, m = 8, 2 ！= 8，所以parent[2] = 8。


  3. begin = 0, end = 1, weight = 10, n = 0, m = 1, 0 != 1 , 所以parent[0] = 1.


  4. begin = 0, end = 5, weight = 11, n = 1, m = 5, 因为parent[0] = 1, parent[1] = 0, 所以n = 1, parent[5] = 0, 所以返回5，即m = 5, n != m， parent[1] = 5。


  5. begin = 1, end = 8, weight = 12, n = 5, m = 8, 因为parent[1] = 5,parent[5] = 0, 返回5，parent[8] = 0, 直接返回8，n != m，parent[5] = 8。


........
........

  1. begin = 5, end = 6, weight = 17, n = 6, m = 6, 因为parent[5] = 8, parent[8] = 6, 所以n = 6, parent[6] = 0, m = 6，n = m， 所以不用修改parent数组，因为V5、V6会形成环路，所以不能将它们加入最小树。
    .....
    .....
    .....
    最终parent数组为下面数组：



    此时，
    parent[0] = 1，V0，V1加入到最小树。
    parent[1] = 5，V1，V5加入到最小树。
    parent[2] = 8，V2，V8加入到最小树。
    parent[3] = 7，V3，V7加入到最小树。
    parent[4] = 7，V4，V7加入到最小树。
    parent[5] = 8，V5，V8加入到最小树。
    parent[6] = 7，V6，V7加入到最小树。
    parent[8] = 6，V8，V6加入到最小树。
    所以所有顶点都加入到最小树中，所以的连线如下图所示：


    最小生成树

代码实现

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

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

/* 对边集数组Edge结构的定义 */
typedef struct
{
    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)
{
    int tempValue;
    
    //交换edges[i].begin 和 edges[j].begin 的值
    tempValue = edges[i].begin;
    edges[i].begin = edges[j].begin;
    edges[j].begin = tempValue;
    
    //交换edges[i].end 和 edges[j].end 的值
    tempValue = edges[i].end;
    edges[i].end = edges[j].end;
    edges[j].end = tempValue;
    
    //交换edges[i].weight 和 edges[j].weight 的值
    tempValue = edges[i].weight;
    edges[i].weight = edges[j].weight;
    edges[j].weight = tempValue;
}

/* 对权值进行排序 */
void sort(Edge edges[],MGraph *G)
{
    //对权值进行排序(从小到大)
    int i, j;
    for ( i = 0; i < G->numEdges; i++)
    {
        for ( j = i + 1; j < G->numEdges; j++)
        {
            if (edges[i].weight > edges[j].weight)
            {
                Swapn(edges, i, j);
            }
        }
    }
    
    printf("边集数组根据权值排序之后的为:\n");
    for (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] > 0)
    {
        f = parent[f];
    }
    return f;
}

/* 生成最小生成树 */
void MiniSpanTree_Kruskal(MGraph G)
{
    int i, j, n, m;
    int sum = 0;
    int k = 0;
    /* 定义一数组用来判断边与边是否形成环路
     用来记录顶点间的连接关系. 通过它来防止最小生成树产生闭环;*/
    
    int parent[MAXVEX];
    /* 定义边集数组,edge的结构为begin,end,weight,均为整型 */
    Edge edges[MAXEDGE];
    
    /*1. 用来构建边集数组*/
    for ( i = 0; i < G.numVertexes-1; i++)
    {
        for (j = i + 1; j < G.numVertexes; j++)
        {
            //如果当前路径权值 != ∞
            if (G.arc[i][j]<INFINITYC)
            {
                //将路径对应的begin,end,weight 存储到edges 边集数组中.
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                
                //边集数组计算器k++;
                k++;
            }
        }
    }
    
    //2. 对边集数组排序
    sort(edges, &G);
    
    
    //3.初始化parent 数组为0. 9个顶点;
    // for (i = 0; i < G.numVertexes; i++)
    for (i = 0; i < MAXVEX; i++)
        parent[i] = 0;
    
    //4. 计算最小生成树
    printf("打印最小生成树：\n");
    /* 循环每一条边 G.numEdges 有15条边*/
    for (i = 0; i < G.numEdges; i++)
    {
        //获取begin,end 在parent 数组中的信息;
        //如果n = m ,将begin 和 end 连接,就会产生闭合的环.
        n = Find(parent,edges[i].begin);
        m = Find(parent,edges[i].end);
        //printf("n = %d,m = %d\n",n,m);
        
        /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */
        if (n != m)
        {
            /* 将此边的结尾顶点放入下标为起点的parent中。 */
            /* 表示此顶点已经在生成树集合中 */
            parent[n] = m;
            
            /*打印最小生成树路径*/
            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;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,324评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,303评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,192评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,555评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,569评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,566评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,927评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,583评论 0赞 257
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,827评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2赞 320
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,365评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,941评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2赞 342

推荐阅读更多精彩内容