红魔咖啡馆


头发越掉越多，头发越掉越少

【图论】最小生成树

  • ~6.11K 字
  1. 1. 最小生成树
    1. 1.1. 定义
    2. 1.2. 性质
    3. 1.3. Prim算法
    4. 1.4. Kruskal算法

最小生成树

定义

生成树：一个连通图的生成树是一个极小的连通子图，包含图中的n个顶点，但只有构成一棵树的n-1条边

最小生成树：对带权图，它的最小生成树即为原图中边权之和最小的生成树

性质

  • 一个连通图可以有多个生成树
  • 所有生成树都包含相同顶点个数和边数
  • 生成树中不存在环，添加一条鞭会构成环
  • 移除生成树中的任意一条边都会导致图的不连通
  • 对于包含个顶点的无向连通图，，生成树包含个顶点和条边，最多包含棵生成树

Prim算法

有一个无向图G，每条边有对应边权，从A顶点开始，寻找一个权值最小的路径使其生成一个极小连通子图

Prim算法即通过加点来构造最小生成树，可以从任何点开始

从A出发，跟A相连的两条路，选权值最小的A-B

此时待选路径有A-F, B-I, B-C, B-G

选择权值最小的路径，即A-F

此时待选路径有B-I, B-C, B-G, F-G, F-E

选择权值最小的路径，即B-I，以此类推

这里我们依次选择了A-B,A-F, B-I, I-C, B-G

此时权值最小的路径为G-F，但如果连上G-F，则形成了环，不符合极小连通子图

选择G-H

最后我们生成了这样的路径，即最小生成树

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
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
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
const int MAX = 0x7fffffff;
typedef char VertexType ;
typedef int EdgeType;
struct mat_grph{
  VertexType vertex[N];
  EdgeType arc[N][N];
  int vertex_num;
  int edge_num;
};
void create_graph(mat_grph* G){
  G->vertex_num = 9;
  G->edge_num = 15;
  G->vertex[0] = 'A';
  G->vertex[1] = 'B';
  G->vertex[2] = 'C';
  G->vertex[3] = 'D';
  G->vertex[4] = 'E';
  G->vertex[5] = 'F';
  G->vertex[6] = 'G';
  G->vertex[7] = 'H';
  G->vertex[8] = 'I';
  for (int i = 0;i<G->vertex_num;i++){
    for (int j = 0;j<G->vertex_num;j++){
      if(i==j) G->arc[i][j] = 0;
      else G->arc[i][j]=MAX;
    }
  }
  G->arc[0][1] = 10;
  G->arc[0][5] = 11;
  G->arc[1][2] = 18;
  G->arc[1][6] = 16;
  G->arc[1][8] = 12;
  G->arc[2][3] = 22;
  G->arc[2][8] = 8;
  G->arc[3][4] = 20;
  G->arc[3][6] = 24;
  G->arc[3][7] = 16;
  G->arc[3][8] = 21;
  G->arc[4][5] = 26;
  G->arc[4][7] = 7;
  G->arc[5][6] = 17;
  G->arc[6][7] = 19;
  // 无向图，把对称的也复制过去
  for (int i = 0;i<G->vertex_num;i++){
    for (int j = 0;j<G->vertex_num;j++){
      G->arc[j][i] = G->arc[i][j];
    }
  }
}
void prim(mat_grph* G){
   int i, j, k;
   int minn;
   int weight[N]; // 侯选边
   int vex_index[N]; // 表示下标和对应值分别代表的顶点间存在一条连线
   // 从顶点A开始
   weight[0]=0; // vex_index某点与下标对应点赋值为0
   vex_index[0]=0;
   for (i = 1;i<G->vertex_num;i++){
    weight[i] = G->arc[0][i]; // 存放第i个节点的待选权值
    vex_index[i] = 0; // 都从0开始连接
  }
  for(int i = 1;i<G->vertex_num;i++){
    minn = MAX;
    j = 0;
    k = 0;
    // 从0到9，寻找最小的与之连接
    for(j=0;j<G->vertex_num;j++){
      if (weight[j]!=0 && weight[j]<minn){
        minn = weight[j];
        k = j;
      }
    }
    cout << G->vertex[vex_index[k]]<<", "<<G->vertex[k]<<endl;
    weight[k]=0; // 该点已被选完，不能再用
    // 找新连接点的待选路径
    for (j = 0;j<G->vertex_num;j++){
      if (weight[j]!=0 && G->arc[k][j]<weight[j]){
        weight[j] = G->arc[k][j]; // 更新备选项
        vex_index[j] = k; // 更新前一个节点的下标为新值
      }
    }
  }

}
int main(){
  mat_grph G;
  create_graph(&G);
  prim(&G);
  return 0;
}

(邻接表/链式前向星)

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 400005; 

struct Edge {
    int to, w, next;
} edge[M]; // 无向图 开两倍

int head[N], cnt;
int dist[N];  // 到生成树的距离
bool vis[N];  // 是否已加入生成树
int parent[N]; // 记录父节点
int n, m, ans;

// 链式前向星加边
void add_edge(int u, int v, int w) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void prim() {
    memset(dist, 0x3f, sizeof dist);
    memset(parent, -1, sizeof parent);
    dist[1] = 0;
    ans = 0;
    
    for(int i = 1; i <= n; i++) {
        int u = 0, minn = 0x3f3f3f3f;
        // 找到距离生成树最近的点
        for(int j = 1; j <= n; j++) {
            if(!vis[j] && dist[j] < minn) {
                minn = dist[j];
                u = j;
            }
        }
        if(u == 0) break;  // 找不到新的点，说明图不连通
        vis[u] = true;
        ans += minn;
        if (parent[u]!=-1) cout <<parent[u] <<" "<<u<<endl; // 非起点输出
        // 更新其他点到生成树的距离
        for(int i = head[u]; ~i; i = edge[i].next) {
            int v = edge[i].to;
            if(!vis[v] && edge[i].w < dist[v]) {
                dist[v] = edge[i].w;
                parent[v]=u;
            }
        }
    }
}

int main() {
    memset(head, -1, sizeof(head));
    cnt = 0;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);  // 无向图需要加两条边
    }
    
    prim();
    bool check = true;
    for(int i = 1; i <= n; i++) {
        if(!vis[i]) {
          check = false;
            break;
        }
    }
    
    if(check) cout << ans << endl;
    else cout << "orz" << endl;
    
    return 0;
}

Kruskal算法

Kruskal算法是通过加边来构建最小生成树的

按边权从小到大排序，最小的是V1-V3

首先判断加入前这两个端点是否在同一个连通分量中，若可以则添加

按边权顺序依次添加V4-V6， V2-V5

此时有两个相同最小边权的情况，证明有多个最小生成树，且都不在同一连通分量，故随便选一个

此时发现，V3与V6已经位于同一连通分量，故不能加边

直到所有点被连通，此时构建了最小生成树

Kruskal算法更适合稀疏图

代码部分使用了并查集来实现判断是否有环

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
#include <bits/stdc++.h>
using namespace std;
const int N = 5005, M = 400005; 

struct Edge {
    int u,v,w;
} edge[M]; // 无向图 开两倍
int parent[N];
int n, m, cnt = 0, ans = 0;
// 查找操作
int find(int x){
  if (parent[x]!=x)parent[x]=find(parent[x]);
  return parent[x];
}
// 合并操作
void merge(int a, int b){
  if (find(a)>find(b)) parent[find(a)]=find(b);
  else parent[find(b)]=find(a);
}

int main(){
  cin >> n >> m;
  // 建图，不需要链式前向星
  for (int i = 1;i<=m;i++){
    int x, y, w;
    cin >> x >> y >> w;
    edge[i] = {x,y,w};
  }
  // 按权值排序
  sort(edge+1,edge+m+1, [&](Edge a, Edge b){return a.w<b.w;});
  for (int i = 1;i<=n;i++) parent[i]=i; // 自己是自己的
  int temp = 0;
  for (int i = 1;i<=m;i++){
    if (find(edge[i].u)==find(edge[i].v)) continue; // 若两者是连通分量则跳过
    else{
      merge(edge[i].u,edge[i].v); // 建边
      temp++; // 记录建的边数
      ans+=edge[i].w; // 累加权值
    }
  }
  if (temp!=n-1) cout <<"orz"; // 若建边数不是n-1，则没有生成最小生成树
  else cout << ans ;
  return 0;
  
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
赞助喵
非常感谢您的喜欢！
赞助喵