首先要感谢
白马书院的姑娘
提供的解题思路和面经。
MST：Minimum Spanning Tree
我都知道你们这些人都不愿意查资料，所以就先讲讲什么是MST。
这还是图论里的概念。
先来解释一下什么是Spanning Tree：
在无向图中，如果存在一颗树，第一，它是这无向图的子图；第二，能够连接图中的所有节点。那么这棵树就称之为Spanning Tree。
Minimum Spanning Tree：
也就是在一个无向有权图（edge-weighted undirected graph）中，存在的一棵spanning tree，不成环的情况下连接所有的节点，并且具有最小权重总和，这颗树，就是MST。（节点数 = N，边数 = N - 1）
那么万恶的亚马逊会绕着弯给你出这个题。
会说，现在过节了，某一个地区有好多个城市（节点），这些城市都有电线互相连接，组成了一个电网（图）。每一条电线都要花钱，而且每一条花的钱都不一样（权重）。地方供电局想花费最小的给所有城市供电，请你给出一个解决方案。
抽象出来就是在无向权重图中找MST的题。我的解法也是根据Kruskal's Algorithm来的（维基百科里面解释得挺好的，有兴趣的同学可以去看看）。
算法里面涉及到Union Find，所以比较繁杂。大家做好准备一起来。
算法的基本思想
由于前一篇Order Dependency有同学说看不懂，我就尽量写得更好一点
先上图：
1.png
这里的MST：
AB,BC,CD三条边组成的spanning tree
再上例子图：
2.png
算法开始了：
首先把所有的边都列出来，根据权重排个序（来来来，写个快排）
大概会成这样：
AD 1
BC 1
DC 1
EF 2
AB 3
BD 3
CF 4
CE 5
同时，所有的节点（vertices）都各自成为独立的disjoint set。大概会成这样：
3.png
算法的基本规则就是：
在排好序的边里，从上往下进行遍历
- 当两个节点不在同一个set中的话，那么把它们分别所在的set合为一个set，并把这条边加入到最终结果中。
- 当两个节点在同一个set中的话，就不用合并，也不用加到最终结果中去。
那就来走一遍例子呗
- 边AD，A和D两个节点都不在同一个set中，那么就把它们合在一起，用set A来代表它们合并后的集合，并且把边AD加入结果里面。大概会成这样：
4.png
- 边BC，B和C也不在同一个set里面，合起来，用set B表示，也加入结果中。大概会成这样：
5.png
- 边DC，这两也不在同一个集合里，合并，用set A来表示。同时也把边DC放入结果中。大概会成这样：
6.png
- 边EF，同理，合并，放入结果，用set E表示。大概也会成这样：
7.png
- 边AB，这两个节点已经在同一个集合里了，忽略。
- 边BD，忽略。
- 边CF，两个节点不在同一个集合里，合并它们所在的集合，并且把边CF放入结果中，合并后的集合用set A来表示。大概是这样：
8.png
- 这估计没人看了，略。
到此，算法就结束了，就找到了这张图的MST了：
AD, BC, DC, EF, CF
最后的权重和为9
说了这么多，上代码：
public class MST {
//给定的类
public static class Connection {
String city1;
String city2;
int cost;
public Connection(String a, String b, int c) {
city1 = a;
city2 = b;
cost = c;
}
}
/**
* 为了避免使用全局变量，声明一个UnionFind类
*/
public static class UnionFind {
Map<String, Integer> map; //map中装的是城市->城市所在的集合代号
int setNum; //城市集合代号
public UnionFind() {
map = new HashMap<>();
setNum = 0;
}
/**
* 对每一个connection做union操作
* 如果没有union操作，返回FALSE，如果有union操作，返回TRUE
* 这里跟算法描述中不太一样：这里合并过的城市才会被分配集合代号
*/
public boolean union(Connection conn) {
// 两个城市都没有城市代号（都存在于单独的集合，都没有被合并过）
if (!map.containsKey(conn.city1) && !map.containsKey(conn.city2)) {
map.put(conn.city1, setNum);
map.put(conn.city2, setNum);
setNum++;
return true;
}
// 有一个城市有代号（说明其中有一个是之前合并过的）
if (map.containsKey(conn.city1) && !map.containsKey(conn.city2)) {
map.put(conn.city2, map.get(conn.city1));
return true;
}
if (!map.containsKey(conn.city1) && map.containsKey(conn.city2)) {
map.put(conn.city1, map.get(conn.city2));
return true;
}
// 两个都有代号（那么合并它们分别所在的集合中的所有城市）
if (map.containsKey(conn.city1) && map.containsKey(conn.city2)) {
int num1 = map.get(conn.city1);
int num2 = map.get(conn.city2);
if (num1 == num2) { //避免出现环
return false;
}
for (String city : map.keySet()) { //把city1在集合中的所有城市代号改为city2的代号
if (map.get(city) == num1) {
map.put(city, num2);
}
}
return true;
}
return false;
}
}
/**
* Time: O(ElogE + E) 后面的 "+E"是在union函数中，当两个城市都有代号的时候
* Space: O(E)
*/
public static List<Connection> findMinimum(List<Connection> list) {
List<Connection> result = new ArrayList<>(); //最终结果，输出必须排序
if (list == null || list.size() == 0) {
return result;
}
UnionFind uf = new UnionFind();
// 首先把边以权重来排序
Collections.sort(list, new Comparator<Connection>() {
@Override
public int compare(Connection conn1, Connection conn2) {
return conn1.cost - conn2.cost;
}
});
// 遍历每一条边，进行处理
for (Connection conn : list) {
if (uf.union(conn)) {
result.add(conn);
}
}
// 最后把结果再排序一次
Collections.sort(result, new Comparator<Connection>() {
@Override
public int compare(Connection conn1, Connection conn2) {
if (conn1.city1.equals(conn2.city1)) {
return conn1.city2.compareTo(conn2.city2);
}
return conn1.city1.compareTo(conn2.city1);
}
});
return result;
}
public static void main(String[] args) {
Connection c1 = new Connection("A", "D", 1);
Connection c2 = new Connection("A", "B", 3);
Connection c3 = new Connection("D", "B", 3);
Connection c4 = new Connection("B", "C", 1);
Connection c5 = new Connection("C", "D", 1);
Connection c6 = new Connection("E", "D", 6);
Connection c7 = new Connection("C", "E", 5);
Connection c8 = new Connection("C", "F", 4);
Connection c9 = new Connection("E", "F", 2);
List<Connection> list = new ArrayList<>(Arrays.asList(c1, c2, c3, c4, c5, c6, c7, c8, c9));
List<Connection> result = findMinimum(list);
for (Connection conn : result) {
System.out.println(conn.city1 + "-" + conn.cost + "-" + conn.city2);
}
}
}
时间复杂度：O(ElogE + E)
空间复杂度：O(E)
这道题没有用全局变量，但是在亚麻的测试中，有两个test case没有通过，要是哪位大神看出错在哪里，请用最蔑视的语气告诉我哪里错了，谢谢了~
看到这儿了都不点个赞，是不是有点说不过去了？
网友评论