美文网首页
算法:最小生成树

算法:最小生成树

作者: 晋阳丶 | 来源:发表于2018-01-13 00:45 被阅读0次

    问题

    给出一些Connections,即Connections类,找到一些能够将所有城市都连接起来并且花费最小的边。
    如果说可以将所有城市都连接起来,则返回这个连接方法;不然的话返回一个空列表。

    注意事项

    返回cost最小的连接方法,如果cost相同就按照city1进行排序,如果city1也相同那么就按照city2进行排序。
    辅助类:

    public class Connection {
        public String city1;
        public String city2;
        public int cost;
        public Connection(String city1, String city2, int cost) {
            this.city1 = city1;
            this.city2 = city2;
            this.cost = cost;
        }
    }
    

    样例

    给出 connections = ["Acity","Bcity",1], ["Acity","Ccity",2], ["Bcity","Ccity",3]
    返回 ["Acity","Bcity",1], ["Acity","Ccity",2]

    思路

    本题一看题目就知道是无向图的最小生成树问题,而解决这个问题有2个著名的算法,Prim算法和Kruskal算法,但是Prim算法在有相同权值的边时会失效,所以此题只能用Kruskal算法来解决。
    Kruskal算法的主要思想是把边按照权值从小到大排序,然后依次取出最小边。

    实现

    public List<Connection> lowestCost(List<Connection> connections) {
            // Write your code here
            connections.sort(new Comparator<Connection>() {
                @Override
                public int compare(Connection o1, Connection o2) {
                    if (o1.cost != o2.cost) {
                        return o1.cost - o2.cost;
                    } else {
                        if (o1.city1.equals(o2.city1)) {
                            return o1.city2.compareTo(o2.city2);
                        } else {
                            return o1.city1.compareTo(o2.city1);
                        }
                    }
                }
            });
    
            Set<String> points = new HashSet<>();
            for (Connection connection : connections) {
                points.add(connection.city1);
                points.add(connection.city2);
            }
    
            List<Connection> result = new ArrayList<>();
            List<Set<String>> pointSets = new ArrayList<>();
            for (String point : points) {
                Set<String> set = new HashSet<>();
                set.add(point);
                pointSets.add(set);
            }
    
            for (Connection connection : connections) {
                String start = connection.city1;
                String end = connection.city2;
                int startIndex = -1;
                int endIndex = -1;
    
                int i = 0;
                for (Set<String> point : pointSets) {
                    if (point.contains(start)) {
                        startIndex = i;
                    }
                    if (point.contains(end)) {
                        endIndex = i;
                    }
                    i++;
                }
    
                if (startIndex < 0 || endIndex < 0) {
                    return new ArrayList<>();
                }
    
                // 比较startIndex和endIndex大小的原因:如果先删除HasHMap较小index的元素,再删除较大Index元素时,会造成数组越界
                // 所以hashSet执行多个remove操作的时候,一定要从后往前删
                if (startIndex > endIndex) {
                    Set<String> startSet = pointSets.get(startIndex);
                    pointSets.remove(startIndex);
                    Set<String> endSet = pointSets.get(endIndex);
                    pointSets.remove(endIndex);
                    startSet.addAll(endSet);
                    pointSets.add(startSet);
                    result.add(connection);
                } else if (startIndex < endIndex) {
                    Set<String> endSet = pointSets.get(endIndex);
                    pointSets.remove(endIndex);
                    Set<String> startSet = pointSets.get(startIndex);
                    pointSets.remove(startIndex);
                    startSet.addAll(endSet);
                    pointSets.add(startSet);
                    result.add(connection);
                }
    
            }
    
            if (pointSets.size() > 1) {
                return new ArrayList<>();
            }
    
            return result;
        }
    

    如果文章对你有帮助的话,不要忘了打赏小编哟

    相关文章

      网友评论

          本文标题:算法:最小生成树

          本文链接:https://www.haomeiwen.com/subject/sibqoxtx.html