技术博客

算法——图的最小生成树

发表于 分类于 阅读次数：
本文字数： 4.9k 阅读时长 ≈ 4 分钟

引言

本文整理了常见的图最小生成树相关算法，方便以后查阅。算法相关的文章均收录于<算法系列文章>。

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
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
package bbm.graph;

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 最小权重生成树
 *
 * 按照边的权重顺序（从小到大）将边加入生成树中，但是若加入该边会与生成树形成环(新加入的边的两个端点在同一个树中)则不加入该边。
 * 直到树中含有V-1条边为止。这些边组成的就是该图的最小生成树。
 *
 * 时间复杂度：E Log E
 *
 * @author bbm
 */
public class Kruskal {

    public static class Line {
        String[] pNames;
        int w;

        public Line(String name1, String name2, int weight) {
            pNames = new String[] {name1, name2};
            w = weight;
        }

        @Override
        public int hashCode() {
            return super.hashCode();
        }

        @Override
        public boolean equals(Object w) {
            return super.equals(w);
        }
    }

    public static void main(String[] args) {
        List<Line> graphLines = new LinkedList<>();
        graphLines.add(new Line("a", "b", 4));
        graphLines.add(new Line("a", "h", 8));
        graphLines.add(new Line("b", "h", 11));
        graphLines.add(new Line("c", "b", 8));
        graphLines.add(new Line("h", "g", 1));
        graphLines.add(new Line("h", "i", 7));
        graphLines.add(new Line("i", "c", 2));
        graphLines.add(new Line("i", "g", 6));
        graphLines.add(new Line("c", "d", 7));
        graphLines.add(new Line("g", "f", 2));
        graphLines.add(new Line("c", "f", 4));
        graphLines.add(new Line("d", "f", 14));
        graphLines.add(new Line("d", "e", 9));
        graphLines.add(new Line("e", "f", 10));
        graphLines.sort(Comparator.comparingInt(o -> o.w));
        // key 表示节点名，value 表示节点所处的树的所有节点
        Map<String, Set<String>> nodeTrees = new HashMap<>();
        for (Line line : graphLines) {
            // 初始化森林
            if (!nodeTrees.containsKey(line.pNames[0])) {
                nodeTrees.put(line.pNames[0], new HashSet<>());
                nodeTrees.get(line.pNames[0]).add(line.pNames[0]);
            }
            if (!nodeTrees.containsKey(line.pNames[1])) {
                nodeTrees.put(line.pNames[1], new HashSet<>());
                nodeTrees.get(line.pNames[1]).add(line.pNames[1]);
            }
            // 如果边的两端不在同一个森林，则加入该边，并将它们的所处的树合并为一个树，同时更新树中所有节点的 nodeTrees
            if (!nodeTrees.get(line.pNames[1]).equals(nodeTrees.get(line.pNames[0]))) {
                System.out.println(line.pNames[0] + "-" + line.pNames[1]);
                nodeTrees.get(line.pNames[1]).addAll(nodeTrees.get(line.pNames[0]));
                nodeTrees.put(line.pNames[0], nodeTrees.get(line.pNames[1]));
                for(String node: nodeTrees.get(line.pNames[1])) {
                    nodeTrees.put(node, nodeTrees.get(line.pNames[1]));
                }
            }
        }
    }
}

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
package bbm.graph;

import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * 最小权重生成树
 *
 * Prim算法的每一步都会为一棵生长中的树添加一条边，该树最开始只有一个顶点，然后会添加V-1个边。
 * 每次总是添加生长中的树和树中除该生长的树以外的部分形成的切分的具有最小权值的横切边(新加入的边一端在树中，一端在树外，并且按照边的权重顺序加入)。
 *
 * 时间复杂度: E + (V log V)
 * @author bbm
 */
public class Prim {
    public static class Line {
        String[] pNames;
        int w;

        public Line(String name1, String name2, int weight) {
            pNames = new String[] {name1, name2};
            w = weight;
        }

        @Override
        public int hashCode() {
            return super.hashCode();
        }

        @Override
        public boolean equals(Object w) {
            return super.equals(w);
        }
    }

    public static void main(String[] args) {
        List<Line> graphLines = new LinkedList<>();
        graphLines.add(new Line("a", "b", 4));
        graphLines.add(new Line("a", "h", 8));
        graphLines.add(new Line("b", "h", 11));
        graphLines.add(new Line("c", "b", 8));
        graphLines.add(new Line("h", "g", 1));
        graphLines.add(new Line("h", "i", 7));
        graphLines.add(new Line("i", "c", 2));
        graphLines.add(new Line("i", "g", 6));
        graphLines.add(new Line("c", "d", 7));
        graphLines.add(new Line("g", "f", 2));
        graphLines.add(new Line("c", "f", 4));
        graphLines.add(new Line("d", "f", 14));
        graphLines.add(new Line("d", "e", 9));
        graphLines.add(new Line("e", "f", 10));
        graphLines.sort(Comparator.comparingInt(o -> o.w));
        Set<String> tree = new HashSet<>();
        tree.add(graphLines.get(0).pNames[0]);
        while (tree.size() < 9) {
            for (Line line: graphLines) {
                // 判断一个边是否一端在树内一端在树外
                if ((tree.contains(line.pNames[0]) && !tree.contains(line.pNames[1]))
                || ((tree.contains(line.pNames[1]) && !tree.contains(line.pNames[0])))) {
                    tree.add(line.pNames[0]);
                    tree.add(line.pNames[1]);
                    System.out.println(line.pNames[0] + "-" + line.pNames[1]);
                    graphLines.remove(line);
                    break;
                } else if (tree.contains(line.pNames[0])) {
                    // 都在树内
                    graphLines.remove(line);
                    break;
                }
            }
        }
    }
}

参考内容

[1] 《算法导论》

贝克街的流浪猫 wechat
您的打赏将鼓励我继续分享!
  • 本文作者： 贝克街的流浪猫
  • 本文链接： https://www.beikejiedeliulangmao.top/algorithm/graph-min-generate-tree/
  • 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议，转载请注明出处！
  • 创作声明： 本文基于上述所有参考内容进行创作，其中可能涉及复制、修改或者转换，图片均来自网络，如有侵权请联系我，我会第一时间进行删除。