前言

  前面对 图的存储 和 **图的遍历（广度优先/深度优先）**做了简单的学习和了解，本篇文章，学习一下最小生成树的问题，以及对应解决这个问题的两种算法 普里姆算法 和 克鲁斯卡尔算法

1.最小生成树问题

首先看下面一道面试题：

假设目前有N个顶点，每个顶点连接的路径不一样，设计一个算法，快速查找出能覆盖所有顶点的路径。

其实这个问题并不是求解两点之间的最短路径，而是设计一个路线，能覆盖所有的顶点。

如下连通图：

那么覆盖所有顶点的路径有一下几种

• 方法一

  V0 ——> V5 ——> V4 --> V3 --> V2 -->V1 -->V8 --> V6 -->V7

  权重：11 + 26 + 20 + 22 + 18 + 21 + 24 + 19 = 161

• 方案二

  V2 ——> V8 ——> V1 --> V0 --> V5 -->V6 -->V7 --> V3 -->V4 权重：8 + 12 + 10 + 11 + 17 + 19 + 16 + 7 = 100

• 方案三

  权重：8 + 12 + 10 + 11 + 16 + 19 + 16 + 7 = 99

由此可以看出，方法三是最优的方案，这就是最小生成树。

最小生成树：把构成连通网的最小代价的生成树称之为最小生成树。即假设有N个顶点，用N-1条边，连接所有顶点，而且权重的和最小的路径。

2.最小生成树求解（普里姆(Prim)算法）

普里姆算法思路：

1. 定义两个数组，adjvew 用来保存相关顶点下标，lowcost 保存顶点之间的权值。
2. 初始化两个数组，将与 V0 相关的 V1-V8 的所有顶点的权值赋值给 lowcost
    adjvew[1-8]，都赋值为 0，表示都是与 V0 相关的顶点（后面循环修改）
3. 循环 lowcost 数组，根据权值，找到权值最新的顶点的下标 k
4. 更新 lowcost 数组
5. 循环所有顶点，找到与下标为 k 的顶点，有关系的顶点，并更新 lowcost  数组和 adjvew 数组


注意：
更新 lowcost 数组的条件
1. 与下标为 k 的顶点之间有连接
2. 当前下标为 j 的顶点是否加入最小生成树
3. 下标为 k 的顶点与下标为 j 的顶点的权值比较，小于，则更新，
    简单说就是要比较之前存储的权值，小于，则更新。
复制代码

接下来，我们详细的解析一下上面的思路：

• 初始化 lowcost 和 adjvew

lowcost 数组（将与 V0 相关的 V1-V8 的所有顶点的权值赋值给 lowcost）

默认将V0加入到最小生成树中，lowcost[0] = 0，10 和 11 表示顶点V0 连接顶点V1和V5的权值。

adjvew 数组（都赋值为 0，表示都是与 V0 相关的顶点）

然后开始循环（从 i = 1 开始，默认第一个已经加入最小树）

• 第一次循环 i = 1

  由上面的表格看出，10 是最小的权值，

  此时，k = 1，在lowcost数组中10最小。且满足更新 lowcost 数组的三个条件，

  所以，lowcost[1] = 0， 表示 V1 已经加入最小生成树，并打印信息

  lowcost 数组

  0	1	2	3	4	5	6	7	8
  0	0	∞	∞	∞	11	∞	∞	∞

  然后，循环所有顶点，找到下标为k顶点各边权值小于此前这些顶点未被加入生成树权值，然后更新lowcost 数组和adjvew 数组

    V2 未加入最小生成树，且权值 18 < ∞，lowcost【2】= 18，adjvew【2】= 1
    V8 未加入最小生成树，且权值 12 < ∞，lowcost【8】= 12，adjvew【8】= 1
    V6 未加入最小生成树，且权值 16 < ∞，lowcost【6】= 16，adjvew【6】= 1
  复制代码

  lowcost 数组

  0	1	2	3	4	5	6	7	8
  0	0	18	∞	∞	11	16	∞	12

  adjvew 数组（都赋值为 0，表示都是与 V0 相关的顶点）

  0	1	2	3	4	5	6	7	8
  0	0	1	0	0	0	1	0	1

  18，16，12对应V2、V6、V8，是针对V1相关的顶点，

  1 是因为 k = 1，表示与V1相连的顶点是V2、V6、V8

• 第二次循环 i = 2

  从 lowcost 中找到 权值最小 11 的 j = 5，便是 k = 5

  所以，lowcost[5] = 0，加入到最小生成树中，并打印信息

  然后，循环所有顶点，找到下标为k = 5顶点各边权值小于此前这些顶点未被加入生成树权值，然后更新lowcost 数组和adjvew 数组

    V6 未加入最小生成树，且权值 17 > 16，不更新
    V4 未加入最小生成树，且权值 26 < ∞，lowcost【4】= 26，adjvew【4】= 5
    V3 未加入最小生成树，且权值 ∞  < ∞，不更新
  复制代码

  此时，lowcost 数组

  0	1	2	3	4	5	6	7	8
  0	0	18	∞	26	0	16	∞	12

  adjvew 数组（都赋值为 0，表示都是与 V0 相关的顶点）

  0	1	2	3	4	5	6	7	8
  0	0	1	0	5	0	1	0	1

  1 ，表示与V1相连的顶点V2、V6、V8，

  5 是因为 k = 5，表示与V5相连的顶点是V4

• 第三次循环 i = 3

  从 lowcost 中找到 权值最小12的 j = 8，便是 k = 8

  所以，lowcost[8] = 0，加入到最小生成树中，并打印信息

  然后，循环所有顶点，找到下标为k = 8顶点各边权值小于此前这些顶点未被加入生成树权值，然后更新lowcost 数组和adjvew 数组

    V2 未加入最小生成树，且权值 8 < 18，lowcost【2】= 8，adjvew【2】= 8
    V3 未加入最小生成树，且权值 21  < ∞，lowcost【3】= 21，adjvew【3】= 8
  复制代码

  此时，lowcost 数组

  0	1	2	3	4	5	6	7	8
  0	0	8	21	26	0	16	∞	0

  V0、V1、V5、V8都已经加入最小生成树

  adjvew 数组（都赋值为 0，表示都是与 V0 相关的顶点）

  0	1	2	3	4	5	6	7	8
  0	0	8	8	5	0	1	0	1

  1 ，表示与V1相连的顶点V6、V8，

  5 ，表示与V5相连的顶点是V4

  8 是因为 k = 8，表示与V8相连的顶点是V2、V3

• 第四次循环 i = 4

  从 lowcost 中找到 权值最小8的 j = 2，便是 k = 2

  所以，lowcost[2] = 0，加入到最小生成树中，并打印信息

  然后，循环所有顶点，找到下标为k = 2顶点各边权值小于此前这些顶点未被加入生成树权值，然后更新lowcost 数组和adjvew 数组

    V3 未加入最小生成树，且权值 22  > 21，不更新
  复制代码

  此时，lowcost 数组

  0	1	2	3	4	5	6	7	8
  0	0	0	21	26	0	16	∞	0

  V0、V1、V5、V8都已经加入最小生成树

  adjvew 数组（都赋值为 0，表示都是与 V0 相关的顶点）

  0	1	2	3	4	5	6	7	8
  0	0	8	8	5	0	1	0	1

  1 ，表示与V1相连的顶点V6、V8， 5 ，表示与V5相连的顶点是V4 8 是因为 k = 8，表示与V8相连的顶点是V2、V3

• 第五次循环 i = 5

  从 lowcost 中找到 权值最小16的 j = 6，便是 k = 6

  所以，lowcost[6] = 0，加入到最小生成树中，并打印信息

  然后，循环所有顶点，找到下标为k = 6顶点各边权值小于此前这些顶点未被加入生成树权值，然后更新lowcost 数组和adjvew 数组

    V7 未加入最小生成树，且权值 19  < ∞，lowcost【7】= 19，adjvew【7】= 6
    V3 未加入最小生成树，且权值 22  > 21，不更新
  复制代码

  此时，lowcost 数组

  0	1	2	3	4	5	6	7	8
  0	0	0	21	26	0	0	19	0

  V0、V1、V2、V5、V6、V8都已经加入最小生成树

  adjvew 数组（都赋值为 0，表示都是与 V0 相关的顶点）

  0	1	2	3	4	5	6	7	8
  0	0	8	8	5	0	1	6	1

  1 ，表示与V1相连的顶点V6、V8，

  5 ，表示与V5相连的顶点是V4

  8 ，表示与V8相连的顶点是V2、V3

  6 是因为 k = 6，表示与V6相连的顶点是V7

• 第六次循环 i = 6

  从 lowcost 中找到 权值最小19的 j = 7，便是 k = 7

  所以，lowcost[7] = 0，加入到最小生成树中，并打印信息

  然后，循环所有顶点，找到下标为k = 7顶点各边权值小于此前这些顶点未被加入生成树权值，然后更新lowcost 数组和adjvew 数组

    V4 未加入最小生成树，且权值 7  < 26，lowcost【4】= 7，adjvew【4】= 7
    V3 未加入最小生成树，且权值 16 < 21，lowcost【3】= 16，adjvew【3】= 7
  复制代码

  此时，lowcost 数组

  0	1	2	3	4	5	6	7	8
  0	0	0	16	7	0	0	0	0

  V0、V1、V2、V5、V6、V7、V8都已经加入最小生成树

  adjvew 数组（都赋值为 0，表示都是与 V0 相关的顶点）

  0	1	2	3	4	5	6	7	8
  0	0	8	7	7	0	1	6	1

  1 ，表示与V1相连的顶点V6、V8，

  8 ，表示与V8相连的顶点是V2

  6 ，表示与V6相连的顶点是V7

  7 是因为 k = 7，表示与V7相连的顶点是V3，V4

• 第七次循环 i = 7 从 lowcost 中找到 权值最小7的 j = 4，便是 k = 4

  所以，lowcost[4] = 0，加入到最小生成树中，并打印信息

  然后，循环所有顶点，找到下标为k = 4顶点各边权值小于此前这些顶点未被加入生成树权值，然后更新lowcost 数组和adjvew 数组

    V3 未加入最小生成树，且权值 20 > 16，不更新
  复制代码

  此时，lowcost 数组

  0	1	2	3	4	5	6	7	8
  0	0	0	16	0	0	0	0	0

  V0、V1、V2、V4、V5、V6、V7、V8都已经加入最小生成树

  adjvew 数组（都赋值为 0，表示都是与 V0 相关的顶点）

  0	1	2	3	4	5	6	7	8
  0	0	8	7	7	0	1	6	1

  1 ，表示与V1相连的顶点V6、V8，

  8 ，表示与V8相连的顶点是V2

  6 ，表示与V6相连的顶点是V7

  7 是因为 k = 7，表示与V7相连的顶点是V3，V4

• 第八次循环 i = 8

  从 lowcost 中找到 权值最小16的 j = 3，便是 k = 3

  所以，lowcost[3] = 0，加入到最小生成树中，并打印信息

  然后，循环所有顶点，找到下标为k = 3顶点各边权值小于此前这些顶点未被加入生成树权值，然后更新lowcost 数组和adjvew 数组

    V3 未加入最小生成树，且权值 20 > 16，不更新
  复制代码

  此时，lowcost 数组

  0	1	2	3	4	5	6	7	8
  0	0	0	0	0	0	0	0	0

  V0、V1、V2、V3、V4、V5、V6、V7、V8都已经加入最小生成树

  adjvew 数组（都赋值为 0，表示都是与 V0 相关的顶点）

  0	1	2	3	4	5	6	7	8
  0	0	8	7	7	0	1	6	1

  1 ，表示与V1相连的顶点V6、V8，

  8 ，表示与V8相连的顶点是V2

  6 ，表示与V6相连的顶点是V7

  7 是因为 k = 7，表示与V7相连的顶点是V3，V4

代码实现：

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

#define MAXEDGE 20
#define MAXVEX  20

typedef  int Status;

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


/* Prim算法生成最小生成树 */
void MiniSpanTree_Prim(MGraph G)
{
    
    int min, i, j, k = 0;
    int sum = 0;
    
    int adjvex[MAXVEX];  // 保存相关顶点下标
    int lowcost[MAXVEX]; // 保存相关顶点的权重
    
    // 初始化第一个权值为0 ，将V0加入生成最小树
    lowcost[0] = 0;
    // 初始化第一个顶点的下标为0
    adjvex[0] = 0;
    
    // 初始化
    for (i = 1; i < G.numVertexes; i++) {
        // 将v0顶点与之有边的权值存入数组
        lowcost[i] = G.arc[0][i];
        // 初始化默认都为v0的下标
        adjvex[i]  = 0;
    }
    
    // 循环除了下标为 0 以外的全部顶点，找到z权重最小且没有加入到s最小树中的顶点
    for (i = 1; i < G.numVertexes; i++) {
        min = INFINITY;
        j = 1; k = 0;
        while (j < G.numVertexes) {
            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];
    
    // 当前顶点的权值设置为0 ，标志为已经加入最小树
    lowcost[k] = 0;
    
    // 循环所有顶点,找到与顶点k 相连接的顶点
    for (j = 1; j < G.numVertexes; j++) {
        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);
}
复制代码

2.最小生成树求解（克鲁斯卡尔算法）

克鲁斯卡尔算法思路：

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

克鲁斯卡尔算法详细解析如下：

设计如下的边表数据结构：

/* 对边集数组Edge结构的定义 */
typedef struct
{
    int begin;   // 开始
    int end;     // 结束
    int weight;  // 权重
}Edge ;
复制代码

那么对上面所说的图的边表，排序后如下：

初始化parent数组，给初始值为0，默顶点间认没有连接

然后开始遍历 排好序的边表：

定义n 和 m ，分别表示begin 和 end，如果 m = n，表示 begin 和 end连接,就会产生闭合的环.

• 第 0 次，i = 0

  begin = 4，end = 7, n = 4, m = 7 n != m，所以parent[4] = 7,然后打印计算权重

parent数组如下：

• 第 1 次，i = 1

  begin = 2，end = 8, n = 2, m = 8

  n != m，所以parent[2] = 8,然后打印计算权重

parent数组如下：

• 第 2 次，i = 2

  begin = 0，end = 1, n = 0, m = 1 n != m，所以parent[0] = 1,然后打印计算权重

parent数组如下：

• 第 3 次，i = 3

  begin = 0，end = 5, n = 0, m = 5

  然后从parent 数组中，找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[0] = 1，所以 n = 1，parent[5] = 0，直接返回 5

  n != m，所以parent[1] = 5,然后打印计算权重

  parent数组如下：

• 第 4 次，i = 4

  begin = 1，end = 8, n = 1, m = 8

  然后从parent 数组中，可以找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[1] = 5，所以 n = 5，parent[8] = 0，直接返回 8

  n != m，所以parent[5] = 8,然后打印计算权重

parent数组如下：

• 第 5 次，i = 5

  begin = 3，end = 7, n = 3, m = 7

  然后从parent 数组中，找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[3] = 0，所以 n = 3，parent[7] = 0，直接返回 7

  n != m，所以parent[3] = 7,然后打印计算权重

  parent数组如下：

• 第 6 次，i = 6

  begin = 1，end = 6, n = 1, m = 6

  然后从parent 数组中，找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[1] = 5，parent[5] = 8，所以 n = 8，parent[6] = 0，直接返回 6

  n != m，所以parent[8] = 6,然后打印计算权重

  parent数组如下：

• 第 7 次，i = 7

  begin = 5，end = 6, n = 5, m = 6

  然后从parent 数组中，找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[5] = 8，parent[8] = 6，所以 n = 6，parent[6] = 0，直接返回 6

  n = m，所以不更新parent数组,所以不能加入最小树

  parent数组如下：

• 第 8 次，i = 8

  begin = 1，end = 2, n = 1, m = 2

  然后从parent 数组中，找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[1] = 5，parent[5] = 8，parent[8] = 6，所以 n = 6，parent[2] = 8，parent[8] = 6，直接返回 m = 6

  n = m，所以不更新parent数组,所以不能加入最小树

  parent数组如下：

• 第 9 次，i = 9

  begin = 6，end = 7, n = 6, m = 7

  然后从parent 数组中，找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[6] = 0，所以 n = 6，parent[7] = 9，直接返回 m = 6

  n != m，所以更新parent数组,所以parent[6] = 7,然后打印计算权重

  parent数组如下：

• 第 10 次，i = 10

  begin = 3，end = 4, n = 3, m = 4

  然后从parent 数组中，找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[3] = 7，parent[7] = 0，所以 n = 7，parent[4] = 7，parent[7] = 0，直接返回 m = 7

  n = m，所以不更新parent数组，所以不能加入最小树

  parent数组如下：

• 第 11 次，i = 11

  begin = 3，end = 8, n = 3, m = 8

  然后从parent 数组中，找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[3] = 7，parent[7] = 0，所以 n = 7，parent[8] = 6，parent[6] = 7，直接返回 m = 7

  n = m，所以不更新parent数组，所以不能加入最小树

  parent数组如下：

• 第 12 次，i = 12

  begin = 2，end = 3, n = 2, m = 3

  然后从parent 数组中，找到当前顶点的尾部下标（ 帮助我们判断2点之间是否存在闭环问题） parent[2] = 8，parent[8] = 6，parent[6] = 7，所以 n = 7，parent[3] = 7，parent[7] = 0，直接返回 m = 7

  n = m，所以不更新parent数组，所以不能加入最小树

  parent数组如下：

• 第 13 次，i = 13

  同上分析，m = n，不更新

• 第 14 次，i = 14 同上分析，m = n，不更新

  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;
// 图结构
typedef struct
{
    int arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
}MGraph;
// 边表结构
typedef struct {
    int begin;
    int end;
    int weight;
}Edge;

/* 交换权值以及头和尾 */
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);
    }
    
}
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 edges[MAXEDGE];
    
    // 构建边表
    for (i = 0; i < G.numVertexes - 1; i++) {
        for (j = 1 + i; 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);
    
    // 初始化parent 数组为0. 9个顶点;
    for (i = 0; i < MAXVEX; i++)
        parent[i] = 0;
    
    // 循环边表
    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);
        
        // n与m不等，说明此边没有与现有的生成树形成环路
        if (n != m) {
            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);
}
复制代码