最小生成树 - Minimum Spanning Tree

Posted on In , Views: Word count in article: 326 Reading time ≈ 1 mins.
  • Prim
  • Kruskal

Prim

Pseudocode

Prim

人话版：

  1. 选择图中最小权重的一条边，构建新树
  2. 找到一条最小权重的，与当前新树中的任意一个节点关联但另一个关联节点不在当前树中的边，且它加入新树后不成环，那么加入这条边
  3. 循环 直到新树中一共有 条边 ()

时间复杂度：

Implement

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
vector<vector<int>> Prim(vector<vector<int>> adjMat) {
  vector<int> dsu(adjMat.size(), -1);
  for (size_t i = 0; i < dsu.size(); i++) {
    dsu[i] = i;
  }
  const function<int(int)> find = [&](int x) {
    return dsu[x] = dsu[x] == x ? x : find(dsu[x]);
  };
  const auto merge = [&](int x, int y) { dsu[find(x)] = dsu[find(y)]; };
  int sumOfweights = 0;
  vector<vector<int>> MSTMat(adjMat.size(), vector<int>(adjMat.size(), 0));
  vector<bool> vis(adjMat.size(), false);
  bool flag = false;
  for (size_t i = 0; i < adjMat.size() - 1; i++) {
    int minu = 0, minv = 0, minw = INT_MAX;
    for (size_t u = 0; u < adjMat.size(); u++)
      for (size_t v = 0; v < adjMat.size(); v++) {
        if (adjMat[u][v] && minw > adjMat[u][v] &&
            (!flag || (vis[u] && !vis[v]) || (vis[v] && !vis[u]))) {
          flag = true;
          minw = adjMat[u][v];
          minu = u;
          minv = v;
        }
      }
    cout << i + 1 << " " << (char)('a' + minu) << " " << (char)('a' + minv)
         << " " << minw << endl;
    vis[minu] = vis[minv] = true;
    merge(minu, minv);
    MSTMat[minu][minv] = MSTMat[minv][minu] = minw;
    adjMat[minu][minv] = adjMat[minv][minu] = 0;
    sumOfweights += minw;
  }
  cout << "Sum of Weights: " << sumOfweights << endl;
  return MSTMat;
}

Kruskal

Pseudocode

Kruskal

人话版：

  1. 找到一条最小权重且它加入新树后不成环的边，加入新树
  2. 循环 直到新树中一共有 条边 ()

时间复杂度：

Implement

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
vector<vector<int>> Kruskal(vector<vector<int>> adjMat) {
  vector<int> dsu(adjMat.size(), -1);
  for (size_t i = 0; i < dsu.size(); i++) {
    dsu[i] = i;
  }
  const function<int(int)> find = [&](int x) {
    return dsu[x] = dsu[x] == x ? x : find(dsu[x]);
  };
  const auto merge = [&](int x, int y) { dsu[find(x)] = dsu[find(y)]; };
  int sumOfweights = 0;
  vector<vector<int>> MSTMat(adjMat.size(), vector<int>(adjMat.size(), 0));
  for (size_t i = 0; i < adjMat.size() - 1; i++) {
    int minu = 0, minv = 0, minw = INT_MAX;
    for (size_t u = 0; u < adjMat.size(); u++)
      for (size_t v = 0; v < adjMat.size(); v++) {
        if (adjMat[u][v] && minw > adjMat[u][v] && find(u) != find(v)) {
          minw = adjMat[u][v];
          minu = u;
          minv = v;
        }
      }
    cout << i + 1 << " " << (char)('a' + minu) << " " << (char)('a' + minv)
         << " " << minw << endl;
    merge(minu, minv);
    MSTMat[minu][minv] = MSTMat[minv][minu] = minw;
    adjMat[minu][minv] = adjMat[minv][minu] = 0;
    sumOfweights += minw;
  }
  cout << "Sum of Weights: " << sumOfweights << endl;
  return MSTMat;
}

Wise-Choice

对于稀疏图，边数较少，采用 Kruskal 比较快，而对于密集图，采用 Prim 较优。

Runable Example

这个实现非常辣鸡，但是你可以凑合看，生成树只需要存边就行了，每条边保存两个节点信息以及权重即可，可以通过小堆实现 的最小权重查找，无需采用邻接矩阵。实现中成环判定采用并查集，每次加入边就把边的两节点合并认为是一个连通块，这样可以实现接近 的成环判定。

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
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> Kruskal(vector<vector<int>> adjMat) {
  vector<int> dsu(adjMat.size(), -1);
  for (size_t i = 0; i < dsu.size(); i++) {
    dsu[i] = i;
  }
  const function<int(int)> find = [&](int x) {
    return dsu[x] = dsu[x] == x ? x : find(dsu[x]);
  };
  const auto merge = [&](int x, int y) { dsu[find(x)] = dsu[find(y)]; };
  int sumOfweights = 0;
  vector<vector<int>> MSTMat(adjMat.size(), vector<int>(adjMat.size(), 0));
  for (size_t i = 0; i < adjMat.size() - 1; i++) {
    int minu = 0, minv = 0, minw = INT_MAX;
    for (size_t u = 0; u < adjMat.size(); u++)
      for (size_t v = 0; v < adjMat.size(); v++) {
        if (adjMat[u][v] && minw > adjMat[u][v] && find(u) != find(v)) {
          minw = adjMat[u][v];
          minu = u;
          minv = v;
        }
      }
    cout << i + 1 << " " << (char)('a' + minu) << " " << (char)('a' + minv)
         << " " << minw << endl;
    merge(minu, minv);
    MSTMat[minu][minv] = MSTMat[minv][minu] = minw;
    adjMat[minu][minv] = adjMat[minv][minu] = 0;
    sumOfweights += minw;
  }
  cout << "Sum of Weights: " << sumOfweights << endl;
  return MSTMat;
}

vector<vector<int>> Prim(vector<vector<int>> adjMat) {
  vector<int> dsu(adjMat.size(), -1);
  for (size_t i = 0; i < dsu.size(); i++) {
    dsu[i] = i;
  }
  const function<int(int)> find = [&](int x) {
    return dsu[x] = dsu[x] == x ? x : find(dsu[x]);
  };
  const auto merge = [&](int x, int y) { dsu[find(x)] = dsu[find(y)]; };
  int sumOfweights = 0;
  vector<vector<int>> MSTMat(adjMat.size(), vector<int>(adjMat.size(), 0));
  vector<bool> vis(adjMat.size(), false);
  bool flag = false;
  for (size_t i = 0; i < adjMat.size() - 1; i++) {
    int minu = 0, minv = 0, minw = INT_MAX;
    for (size_t u = 0; u < adjMat.size(); u++)
      for (size_t v = 0; v < adjMat.size(); v++) {
        if (adjMat[u][v] && minw > adjMat[u][v] &&
            (!flag || (vis[u] && !vis[v]) || (vis[v] && !vis[u]))) {
          flag = true;
          minw = adjMat[u][v];
          minu = u;
          minv = v;
        }
      }
    cout << i + 1 << " " << (char)('a' + minu) << " " << (char)('a' + minv)
         << " " << minw << endl;
    vis[minu] = vis[minv] = true;
    merge(minu, minv);
    MSTMat[minu][minv] = MSTMat[minv][minu] = minw;
    adjMat[minu][minv] = adjMat[minv][minu] = 0;
    sumOfweights += minw;
  }
  cout << "Sum of Weights: " << sumOfweights << endl;
  return MSTMat;
}

int main() {
  vector<vector<int>> adjMat = {
      //        a  b  c  d  e  f  g  h  i  j  k  l
      /*0  a*/ {0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0},
      /*1  b*/ {2, 0, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0},
      /*2  c*/ {0, 3, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0},
      /*3  d*/ {0, 0, 1, 0, 0, 0, 0, 5, 0, 0, 0, 0},
      /*4  e*/ {3, 0, 0, 0, 0, 4, 0, 0, 4, 0, 0, 0},
      /*5  f*/ {0, 1, 0, 0, 4, 0, 3, 0, 0, 2, 0, 0},
      /*6  g*/ {0, 0, 2, 0, 0, 3, 0, 3, 0, 0, 4, 0},
      /*7  h*/ {0, 0, 0, 5, 0, 0, 3, 0, 0, 0, 0, 3},
      /*8  i*/ {0, 0, 0, 0, 4, 0, 0, 0, 0, 3, 0, 0},
      /*9  j*/ {0, 0, 0, 0, 0, 2, 0, 0, 3, 0, 3, 0},
      /*10 k*/ {0, 0, 0, 0, 0, 0, 4, 0, 0, 3, 0, 1},
      /*11 l*/ {0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 1, 0},
  };
  auto MSTMat = Prim(adjMat);
  cout << "Prim:" << endl;
  cout << "  a b c d e f g h i j k l" << endl;
  for (size_t u = 0; u < MSTMat.size(); u++) {
    cout << (char)('a' + u) << " ";
    for (size_t v = 0; v < MSTMat.size(); v++) cout << MSTMat[u][v] << " ";
    cout << endl;
  }
  MSTMat = Kruskal(adjMat);
  cout << "Kruskal:" << endl;
  cout << "  a b c d e f g h i j k l" << endl;
  for (size_t u = 0; u < MSTMat.size(); u++) {
    cout << (char)('a' + u) << " ";
    for (size_t v = 0; v < MSTMat.size(); v++) cout << MSTMat[u][v] << " ";
    cout << endl;
  }
  return 0;
}