数据结构（19）图的最小生成树算法

前言

在有n个顶点的图中，要连接所有顶点，只需要n-1条线路。假设每假设一条线路都需要付出一定代价，并且每条线路的代价不一定相同，那么就引出一个新的问题：如何设置线路，使得所有线路的总代价最小呢？

一个连通图的生成树是一个极小的连通子图，它含有图中的全部顶点，但是只有足以构成一棵树的n-1条边；当某棵生成树所拥有的n-1条边的代价总和为最小时，称其为最小生成树。

如何找到这样一棵最小生成树呢？主要有两种算法，即普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。

普里姆（Prim）算法

普里姆算法的思想是：从已纳入生成树的顶点集合出发，找到下一个可以到达并且花费代价为最小的顶点，若它不在生成树中，则将其纳入生成树。

显然，算法要求先拥有一个生成树的顶点集合，这意味着在调用算法时，需要指定一个初始的顶点，先把它纳入集合中。

以上图为例，假设初始顶点为A，那么普里姆算法是如何寻找最小生成树的呢？

1. 首先，将A顶点纳入顶点集合中，此时可以到达的顶点为B、C、D，其中花费代价最小的顶点为C（A-C），并且C不在顶点集合中，则将C纳入生成树

2. A、C在顶点集合中，此时可以到达的顶点为B、D、E、F，其中花费代价最小的顶点为F（C-F），并且F不在顶点集合中，则将F纳入生成树

3. A、C、F在顶点集合中，此时可以到达的顶点为B、D、E，其中花费代价最小的顶点为D（F-D），并且D不在顶点集合中，则将D纳入生成树

4. A、C、D、F在顶点集合中，此时可以到达的顶点为B、E，其中花费代价最小的顶点为B（C-B），并且B不在顶点集合中，则将B纳入生成树

5. A、B、C、D、F在顶点集合中，此时可以到达的顶点为E，其中花费代价最小的顶点为E（B-E），并且E不在顶点集合中，则将E纳入生成树

这样我们就获得了一个最小生成树，每个顶点之间边的权值总和最小。

那么，如何实现这个算法呢？

可以发现，我们只关心生成树的顶点集合到剩余顶点的最小花费。例如，在C顶点加入顶点集合后，顶点集合到B顶点有两条边，即A-B（6）与C-B（5），如果此时需要选择一条连接B顶点，必然会选择C-B；即使以后出现比C-B花费更少的边，也与A-C边无关。

也就是说，我们可以维护一个lowCost数组，它记录了顶点集合到每个顶点的最小花费，如果顶点已经在集合中，则花费为0；如果有未能到达的顶点，则花费为max；否则存放顶点集合中的某个顶点到它的花费（这条线路的花费是最小的）。

那么问题来了：当顶点集合有多个顶点时，我们怎么知道是哪个顶点到目标顶点的花费呢？因此还需要维护一个mst数组，来记录lowCost中的花费，是从哪个顶点出发产生的。

这样，当有新的顶点纳入生成树时，首先将lowCost数组中该顶点的花费置为0，然后从该顶点出发，重新计算到达每个顶点的花费，如果小于已存在的花费，则修改lowCost数组和mst数组的数据。

然后，再遍历新的lowCost数组，找到下一个花费最小的顶点，将其纳入生成树。

实现普里姆算法的整体思路是：

• 将两个辅助数组创建好
• 获取到初始顶点的位置，将其纳入生成树中（这个过程相当于初始化两个辅助数组
• 开始遍历lowCost数组，每次找到最小花费可到达的顶点，将该顶点纳入生成树（重新计算顶点集合到每个顶点的最小花费）
• 有n个顶点，则需要找到n-1条边，即循环n-1次

//获取两个顶点的距离
int GetWeight(GraphMtx *g,int v1,int v2){
   
    if (v1 == -1 || v2 == -1) {
   
        return DEFAULT_MAX_COST;
    }
    return g->Edge[v1][v2];
}
//最小生成树-普里姆算法
void MinSpanTree_Prim(GraphMtx *g,T vertex){
   
    
    //辅助数组->记录最小的花费
    int *lowCost = (int*)malloc(sizeof(int)*g->NumVertices);
    assert(lowCost != NULL);
    //辅助数组->记录起始顶点
    int *mst = (int *)malloc(sizeof(int)*g->NumVertices);
    assert(mst != NULL);
    
    //获得起始位置
    int k = GetVertexPos(g, vertex);
    //将初始顶点纳入生成树->初始化辅助数组中的数据
    for (int i = 0; i < g->NumVertices; i ++) {
   
        if (i != k) {
   
            lowCost[i] = GetWeight(g, k, i);
            mst[i] = k;
        }else{
   
            lowCost[i] = 0;
        }
    }
    
    
    int min,minIndex;
    int begin,end;
    int cost;
    for (int i = 0; i < g->NumVertices-1; i ++) {
   
        min = DEFAULT_MAX_COST;
        minIndex = -1;
        //找到当前最小花费可到达的顶点
        for (int j = 0; j < g->NumVertices; j ++) {
   
            if (lowCost[j] != 0 && lowCost[j] < min) {
   
                //如果它没有存在于顶点集合中->找到了
                min = lowCost[j];
                minIndex = j;
            }
        }
        //找到到达该顶点的起始点
        begin = mst[minIndex];
        end = minIndex;
        //输出信息
        printf("%c->%c:%d\n",g->VerticesList[begin],g->VerticesList[end],min);
        
        //将该顶点纳入生成树
        lowCost[minIndex] = 0;
        //重新计算到达每个顶点的最小花费
        for (int j = 0; j < g->NumVertices; j ++) {
   
            cost = GetWeight(g, minIndex, j);
            if (cost < lowCost[j]) {
   
                //该顶点的花费比已存的花费少->更新数据
                lowCost[j] = cost;
                mst[j] = minIndex;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

克鲁斯卡尔（Kruskal）算法

如果说，普里姆算法是从顶点出发，去寻找顶点，那么克鲁斯卡尔算法出发则是从边出发来寻找顶点。

其基本思想是：每次寻找当前花费最小的一条边，若该边的两条顶点不在同一个连通子图上，则将其加入到生成树中。

如图所示

1. 首先找到当前花费最小的边A-C，A、C顶点不在同一个连通子图上，将其加入生成树中

2. 找到当前花费最小的边D-F，D、F顶点不在同一个连通子图上，将其加入生成树中

3. 找到当前花费最小的边B-E，B、E顶点不在同一个连通子图上，将其加入生成树中

4. 找到当前花费最小的边C-F，C、F顶点不在同一个连通子图上，将其加入生成树中

5. 找到当前花费最小的边，此时有三条边代价相等，即B-C、A-D、C-D，选择任意一条边即可。

   但是可以发现，此时A、C、D顶点在同一个连通子图上，显然不能连接。因此最终选择B-C边，加入生成树中

这样，同样可以得到一棵最小生成树。

那么，如何判断两个顶点是否在同一个连通子图呢？

我们可以设置一个father数组，用于记录每一个顶点的父结点，假如两个顶点拥有相同的父结点，则说明是在同一个连通子图上。假如顶点的父结点是它本身，说明该顶点就是一个连通子图的根；若不是它本身，则说明它之上还有父结点，则继续向上查找。

• 当father数组初始化时，每个顶点的父结点都是它本身，说明此时每个顶点都是相互独立的。

• 将A-C边纳入生成树中，则令C顶点的父结点为A（反之亦可），此时A、C顶点连成一个连通子图，之后的D-F、B-E边同理

• 将C-F纳入生成树中，先判断C的父结点（A）与F的父结点（F）是否是同一个，不是则可以纳入；令F的父结点的父结点等于C的父结点（反之亦可），这样A-C-F-D连成了一个连通子图

  注：假设，F的父结点为D，而D的父结点为它本身，则C-F连接时，是令F的父结点（D）的父结点等于C的父结点（A）。相反地，也可以让C的父结点（A）的父结点等于F的父结点（D）

  注注：假设此时，想插入A-D边，则查找A的父结点（A）与D的父结点。虽然father数组中D的父结点为F，但是F的父结点不是它本身，说明其上还有父结点，则继续寻找到F的父结点（A），则A与D拥有同一个父结点，说明是在同一个连通子图中，无法插入

• 将B-C纳入生成树中，先判断C的父结点（A）与B的父结点（B）是否是同一个，不是则可以纳入；令B的父结点的父结点等于C的父结点（反之亦可），这样A-B-C-D-E-F连成了一个连通子图

可见，克鲁斯卡尔算法有两个主要部分：第一个即判断两个结点的父结点是否是同一个，第二是使一个顶点的父结点的父结点等于另一个顶点的父结点（也就是将两个连通子图连在一起）

int Is_same(int *father,int i,