最小生成树(minimum spanning tree)


适用组别:提高组
难度系数:6


树的定理:N个结点用N-1条边连接成一个连通块,形成的图形只可能是树。

生成树的概念:

一个有N个结点的连通图,边一定是大于或等于N-1条边,在这些边中选择N-1条出来,连接所有的N个点, 称为生成树(spanning tree)。

生成树的特性:
1、包含连通图中所有的顶点;
2、任意两顶点之间有且仅有一条通路;
3、边数=顶点数-1
4、连通图的生成树不唯一


最小生成树:
如果这N-1条边的边权之和是所有方案中最小的,则称之为最小生成树(minimum spanning tree)。
最小生成树只在无向图中有,有向图没有最小生成树的概念。

一、最小生成树与最短路径树的区别

最小生成树能够保证整个拓扑图的所有路径之和最小,但不能保证任意两点之间是最短路径。

下图中,右下角的图就是橙色图的最小生成树


一、pirm算法

该算法从顶点的角度为出发点,时间复杂度为O(n2),更适合与解决边的绸密度更高的连通网。是一种贪心算法。






具体代码实现如下:

 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
75
76
77
78
79
80
81
82
83
84
/**************************************************************** 
 * Description: 使用 Prim 算法来实现最小生成树(MST)
 * Author: Alex Li
 * Date: 2024-01-31 04:01:34
 * LastEditTime: 2024-01-31 04:15:02
****************************************************************/
#include <iostream>
using namespace std;

// 定义图的顶点数
#define V 5

// 找到未包含在MST中、键值最小的顶点
int minKey(int key[], bool mstSet[]){
    // 初始化最小值
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;

    return min_index;
}

// 打印构建的MST,它存储在parent[]数组中
void printMST(int parent[], int graph[V][V]){
    cout << "Edge \tWeight\n";
    for (int i = 1; i < V; i++)
        cout << parent[i] << " - " << i << " \t"
             << graph[i][parent[i]] << " \n";
}

// 函数用于构造并打印由邻接矩阵表示的图的MST
void primMST(int graph[V][V]){
    
    int parent[V];// 存储构建的MST
    int key[V]; // 键值数组,用于选择最小权重边
    bool mstSet[V]; // 表示已包含在MST中的顶点集合

    // 初始化所有键值为无穷大
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    // 总是将第一个顶点包含在MST中,将键值设置为0,使得该顶点成为第一个被选中的顶点
    key[0] = 0;
   
    // 第一个节点总是MST的根
    parent[0] = -1;

    // MST将有V个顶点
    for (int count = 0; count < V - 1; count++) {
         
        // 从未包含在MST中的顶点集合中选出键值最小的顶点
        int u = minKey(key, mstSet);

        // 将选出的顶点添加到MST集合中
        mstSet[u] = true;
 
        // 更新相邻顶点的键值和父索引只考虑那些尚未包含在MST中的顶点
        for (int v = 0; v < V; v++)
// graph[u][v]仅对mstSet[v]为false的相邻顶点非零, 只有当graph[u][v]小于key[v]时,才更新键值
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }
 
    // 打印构建的MST
    printMST(parent, graph);
}
 
// 主函数
int main()
{
    // 图的邻接矩阵表示
    int graph[V][V] = { { 0, 2, 0, 6, 0 },
                        { 2, 0, 3, 8, 5 },
                        { 0, 3, 0, 0, 7 },
                        { 6, 8, 0, 0, 9 },
                        { 0, 5, 7, 9, 0 } };
 
    // 打印解决方案
    primMST(graph);
 
    return 0;
}


二、Kruskal算法

Kruskal算法,从边的角度求网的最小生成树,时间复杂度为O(eloge)。和prim算法恰恰相反,更适合于求边稀疏的网的最小生成树。






代码实现:

 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
/**************************************************************** 
 * Description:  C++ code to implement Kruskal's algorithm
 * Author: Alex Li
 * Date: 2023-05-17 09:53:47
 * LastEditTime: 2024-01-31 04:54:05
****************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000;

// 用于记录节点的集合,避免形成环路
int parent[N];
// n 为顶点数,m 为边的数量
int ans, n, m;

struct Edge {  // 存储边的权重
    int head;
    int tail;
    int weight;
} edge[N];

// 边的比较函数,用于排序
bool cmp(Edge a, Edge b){
    return a.weight < b.weight;
}

void Kruscal(){
    sort(edge, edge + m, cmp);  // 对边进行排序
    for (int i = 1; i <= n; i++) parent[i] = i; // 初始化各顶点的父节点
    for (int i = 0; i < m; i++) {
        int pos1 = edge[i].head;
        int pos2 = edge[i].tail;
        // 检查两个顶点是否属于不同的集合,以避免环路的形成
        if (parent[pos1] != parent[pos2]) {
            ans += edge[i].weight; // 将边的权重加到总和中
            int maxx = max(parent[pos1], parent[pos2]);
            int minn = min(parent[pos1], parent[pos2]);
            // 将已选择的节点集合中较大编号统一更新为较小编号
            for (int j = 1; j <= n; j++) {
                if (parent[j] == maxx) parent[j] = minn;
            }
        }
    }   
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i++) { // 输入边的信息
        int u, v, w;  // u 和 v 为顶点,w 为权重
        cin >> u >> v >> w; // 输入边的相关信息
        edge[i].head = u;
        edge[i].tail = v;
        edge[i].weight = w; // 将信息存储到结构体中
    }
    Kruscal(); // 执行 Kruskal 算法
    cout << ans; // 输出最小生成树的权重和
}
Scroll to Top