算法-最小生成树

发表于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

概述

最小生成树 属于图论用语，它是连通图中具有最小边代价和的生成树。求取它的实际意义在于：如果需要为城镇部署线网，按照最小生成树进行部署，既可保证用户全覆盖，又可保证代价最小。

我们在此介绍两种最小生成树求解算法 —— Prim 算法 (又称 “加点法”) 和 Kruskal 算法 (又称 “加边法”)。

Prim 算法

Prim 算法步骤描述如下 (假定图中节点集合为 $V$)：

  1. 选定图中某一节点为根节点，记为 $root$。
  2. 构建两个集合 $S$ 和 $T$ ($S$ 表示节点集合中属于最小生成树中节点的节点集，$T$ 表示节点集合中不属于最小生成树中节点的节点集)，并初始化它们为 $S = {root}, T = V - {root}$。
  3. 选择 $T$ 中距离 $S$ 中节点最近的节点，将其从 $T$ 中删去并加入到 $S$ 中。
  4. 循环迭代步骤 3，直至 $S == V$。
  • 从步骤描述中可以看到：需要时刻维护 $T$ 中节点到 $S$ 中节点的距离 (即边代价)。
  • 最小生成树基于添加点而构建，故而其称为 “加点法”。
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
// 如果边权重为INF，表明该边不存在。
public static int INF = 0x3fffffff;

public int[] prim(int[][] graph) {
    // 维护T中节点到S中节点的边代价
    int[] destination = new int[graph.length];
    int[] distance = new int[graph.length];

    // 默认使用0号节点作为最小生成树树根，首先初始化相关信息。
    for (int i = 0; i < graph[0].length; i++) {
        destination[i] = 0;
        distance[i] = graph[0][i];
    }
    distance[0] = 0;

    // 循环迭代以构建最小生成树。
    for (int i = 1; i < graph.length; i++) {
        int minIndex = 0;
        int minDistance = INF;

        // 找到T中最小代价边。
        for (int j = 0; j < distance.length; j++) {
            if (distance[j] != 0 && distance[j] < minDistance) {
                minIndex = j;
                minDistance = distance[j];
            }
        }

        distance[minIndex] = 0;

        // 依据最小代价边更新信息。
        for (int j = 0; j < distance.length; j++) {
            if (distance[j] != 0 && distance[j] > graph[minIndex][j]) {
                destination[j] = minIndex;
                distance[j] = graph[minIndex][j];
            }
        }
    }

    return destination;
}

Kruskal 算法

Kruskal 算法步骤描述如下 (假定图中节点集合为 $V$)：

  1. 将图中所有边按照边代价从小到大进行排序。
  2. 清空图中所有边，使得图仅剩所有顶点。
  3. 从小到大依次选择边，如果该边对应的两个顶点已经连通，则不作任何处理，否则在图中添加此边。
  4. 循环迭代步骤 3， 直至图中添加地边数为 $V.size - 1$。
  • 判断顶点是否连通，可使用并查集快速做到。
  • 最小生成树基于添加边而构建，故而其称为 “加边法”。
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
// 边信息(包含起止点、边代价)，用于排序及最后输出记录。
class EdgeInfo {
    int distance;
    int i;
    int j;

    public EdgeInfo(int distance, int i, int j) {
        this.distance = distance;
        this.i = i;
        this.j = j;
    }
}

public ArrayList<EdgeInfo> kruskal(int[][] graph) {
    // 并查集，用于判断两点是否连通。
    UnionFind uf = new UnionFind(graph.length);
    // 存放最小生成树记录。
    ArrayList<EdgeInfo> result = new ArrayList<>();
    // 使用优先队列按照边代价对图中所有边从小到大排序。
    PriorityQueue<EdgeInfo> edges = new PriorityQueue<>((o1, o2) -> {
        EdgeInfo edge1 = (EdgeInfo) o1;
        EdgeInfo edge2 = (EdgeInfo) o2;
        return (edge1.distance - edge2.distance);
    });

    // 初始化优先队列。
    for (int i = 0; i < graph.length; i++) {
        for (int j = 0; j < graph[0].length; j++) {
            if (graph[i][j] != INF) {
                edges.add(new EdgeInfo(graph[i][j], i, j));
            }
        }
    }

    int k = 0;
    while (!edges.isEmpty()) {
        EdgeInfo tmp = edges.remove();

        // 边对应的两个顶点不连通，则合并之，同时将该边置于最终结果。
        if (uf.find(tmp.i) != uf.find(tmp.j)) {
            uf.union(tmp.i, tmp.j);
            result.add(tmp);
            k++;
        }

        // 如果结果集中已有v.size-1条边，则最小生成树已构建完成，退出循环。
        if (k == graph.length - 1) {
            break;
        }
    }

    return result;
}