算法：最小生成树(Minimum Spanning Tree)

发表于 更新于 分类于 阅读次数： 本文字数： 6.2k 阅读时长 ≈ 6 分钟

生成树指的是一个连通图G的覆盖所有顶点的无环子图，最小生成树指的是所有生成树中加权和最小的生成树。

最小生成树的应用：聚类分析、网络架构设计、VLSI布线设计等诸多实际应用问题，都可转化并描述为最小支 撑树的构造问题。在这些应用中，边的权重大多对应于某种可量化的成本，因此作为对应优化问 题的基本模型，最小支撑树的价值不言而喻。——《数据结构C++版》

求最小支撑树的算法主要采用贪心算法，最著名的两个算法分别是Prim算法和Kruskal算法。

本篇主要参考Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2 - GeeksforGeeks以及以及Prim’s Minimum Spanning Tree (MST) | Greedy Algo-5 - GeeksforGeeks，GeeksforGeeks上的数据结构今天刚好搜到了，确实讲的不错，转载收藏一下作为笔记。

Prim算法

使用Prim算法之前，需要了解图论中的一个概念。割(Cut or Cross edges )指的是连接两个子图的边。Prim算法从图中的任意一个点出发，选出所有割中的最小边加入到MST中，直到所有的顶点都在MST中。算法的思想很简单，代码如下

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// A C++ program for Prim's Minimum
// Spanning Tree (MST) algorithm. The program is
// for adjacency matrix representation of the graph
#include <bits/stdc++.h>
using namespace std;

// Number of vertices in the graph
#define V 5

// A utility function to find the vertex with
// minimum key value, from the set of vertices
// not yet included in MST
int minKey(int key[], bool mstSet[])
{
    // Initialize min value
    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;
}

// A utility function to print the
// constructed MST stored in 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";
}

// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
    // Array to store constructed MST
    int parent[V];

    // Key values used to pick minimum weight edge in cut
    int key[V];

    // To represent set of vertices included in MST
    bool mstSet[V];

    // Initialize all keys as INFINITE
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

    // Always include first 1st vertex in MST.
    // Make key 0 so that this vertex is picked as first
    // vertex.
    key[0] = 0;
    parent[0] = -1; // First node is always root of MST

    // The MST will have V vertices
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum key vertex from the
        // set of vertices not yet included in MST
        int u = minKey(key, mstSet);

        // Add the picked vertex to the MST Set
        mstSet[u] = true;

        // Update key value and parent index of
        // the adjacent vertices of the picked vertex.
        // Consider only those vertices which are not
        // yet included in MST
        for (int v = 0; v < V; v++)

            // graph[u][v] is non zero only for adjacent
            // vertices of m mstSet[v] is false for vertices
            // not yet included in MST Update the key only
            // if graph[u][v] is smaller than key[v]
            if (graph[u][v] && mstSet[v] == false
                && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }

    // print the constructed MST
    printMST(parent, graph);
}

// Driver's code
int main()
{
    /* Let us create the following graph
        2 3
    (0)--(1)--(2)
    | / \ |
    6| 8/ \5 |7
    | / \ |
    (3)-------(4)
            9	 */
    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 } };

    // Print the solution
    primMST(graph);

    return 0;
}

// This code is contributed by rathbhupendra

这里的代码主要使用的是图的邻接矩阵表示，采用的思想是维护一个与剩余的子图相连的割的数组，在添加边的时候更新这个数组，每次添加的时候就可以从这个数组中寻找最小的割，时间复杂度为O(V^2)，还有另外一种邻接表的表示方法，使用邻接表和优先队列可以将时间复杂度降为O(E log V)，更加复杂一些，参考Prim’s MST for Adjacency List Representation | Greedy Algo-6 - GeeksforGeeks。

Kruskal算法

首先，将G中的所有边E按照权重从小到大进行排序，然后依次遍历，如果将当前的边加入当前的子图中不会产生环，那么就加入当前的边，否则继续遍历下一个最小边，直到所有的边都被遍历。这里产生的一个问题就是如何判断是否是有环图，这里我们可以是用压缩路径的并查集算法，参考Union-Find Algorithm | Set 2 (Union By Rank and Path Compression) - GeeksforGeeks，代码如下。

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>

using namespace std;

typedef struct node {
    int rank;
    int parent;
} Node;

class Union {
private:
    node *nodes;

public:
    explicit Union(int n) {
        nodes = new node[n];
        for (int i = 0; i < n; ++i) {
            nodes[i].rank = 1;
            nodes[i].parent = i;
        }
    }

    ~Union() {
        delete nodes;
    }

    int find(int i) {
        if (nodes[i].parent != i)
            nodes[i].parent = find(nodes[i].parent);
        return nodes[i].parent;
    }

    void merge(int i, int j) {
        int i_root = find(i);
        int j_root = find(j);
        if (nodes[i_root].rank < nodes[j_root].rank) {
            nodes[i_root].parent = nodes[j_root].parent;
        } else if (nodes[i_root].rank > nodes[j_root].rank) {
            nodes[j_root].parent = nodes[i_root].parent;
        } else if (nodes[i_root].parent != nodes[j_root].parent) {
            nodes[j_root].parent = nodes[i_root].parent;
            nodes[i_root].rank += 1;
        }
    }
};

class Graph {
private:
    vector<vector<int>> edgelist;
    int V;
public:
    explicit Graph(int v) { this->V = v; }

    vector<vector<int>> get_edgelist() const { return edgelist; }

    int get_size() const { return V; }

    void add_edge(int source, int destination, int weight) { edgelist.push_back({weight, source, destination}); }

    void add_edge(vector<int> edge) { edgelist.push_back(edge); }

    int get_total_weights() {
       int sum = 0;
       for (vector<int> edge : edgelist) {
           sum += edge[0];
       }
       return sum;
    }

    static Graph kruskals_mst(const Graph& graph) {
        vector<vector<int>> edgelist = graph.get_edgelist();
        sort(edgelist.begin(), edgelist.end());
        Union s(graph.get_size());
        Graph mst = Graph(graph.get_size());
        for (vector<int> edge: edgelist) {
            // determine whether put the edge into mst will cause a cycle
            // if the two vertices do not belong to the same root
            // they will introduce a cycle
            if (s.find(edge[1]) != s.find(edge[2])) {
                // merge the two subsets together
                s.merge(edge[1], edge[2]);
                mst.add_edge(edge);
                cout << edge[1] << " -- " << edge[2] << " == " << edge[0] << endl;
            }
        }
        return mst;
    }
};

int main()
{
    /* Let us create following weighted graph
                   10
              0--------1
              |  \     |
             6|   5\   |15
              |      \ |
              2--------3
                  4       */
    Graph g(4);
    g.add_edge(0, 1, 10);
    g.add_edge(1, 3, 15);
    g.add_edge(2, 3, 4);
    g.add_edge(2, 0, 6);
    g.add_edge(0, 3, 5);

    // Function call
    Graph::kruskals_mst(g);
    return 0;
}

参考资料

  1. 《数据结构C++版-邓俊辉》6.11 最小支撑树
  2. Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2 - GeeksforGeeks
  3. Prim’s Minimum Spanning Tree (MST) | Greedy Algo-5 - GeeksforGeeks
  4. Union-Find Algorithm | Set 2 (Union By Rank and Path Compression) - GeeksforGeeks
  5. Prim’s MST for Adjacency List Representation | Greedy Algo-6 - GeeksforGeeks
  6. 算法学习笔记(1) : 并查集 - 知乎 (zhihu.com)