算法分析设计-贪心算法

一. 前言

贪心算法（Greedy Algorithm）

贪心算法就是通过一系列局部最优选择得到整体问题的一个解的算法。但并不总是得到最优解。

重点是明白一个问题的贪心选择策略。

二. 切木材问题

1.题目描述

给一个长度为17的木材，可以切成小段卖出去，价格根据小段的长度不同而不同。

Length	i	1	2	3	4	5	6	7	8	9	10
Price	pi	1	4	5	7	10	17	17	20	24	30

如何通过切成小段卖出尽可能高的总价钱?

2.代码实现

public class RodPiece implements Comparable<RodPiece> {
    //木块的长度
    int length;
    //木块对应的价值
    int value;

    //构造方法
    public RodPiece(int length, int value) {
        this.length = length;
        this.value = value;
    }

    @Override
    public int compareTo(RodPiece rodPiece) {
        if ((double)value / (double)length - (double)rodPiece.value / (double)rodPiece.length > 0){
            return 1;
        }else if ((double)value / (double)length - (double)rodPiece.value / (double)rodPiece.length < 0) {
            return -1;
        }else {
            return 0;
        }
    }
}

public class RodCut {
    /**
     * 切木块-贪心
     *
     * @param cut_values
     * @param rod_length
     * @return
     */
    public static int getValueByGreedy(int[] cut_values, int rod_length) {
        //木块价值表的长度
        int n = cut_values.length;

        //存储木块价值表中每一个对应的RodPiece
        RodPiece[] rod_pieces = new RodPiece[n];
        //初始化
        for (int i = 0; i < n; i++) {
            rod_pieces[i] = new RodPiece(i + 1, cut_values[i]);
        }

        //从大到小排序
        Arrays.sort(rod_pieces, Collections.<RodPiece>reverseOrder());

        //记录价值
        int value = 0;

        //贪心寻找
        for (int i = 0; i < n; i++) {
            //能切成当前木块几次就切几次
            value += rod_pieces[i].value * (rod_length / rod_pieces[i].length);

            //木块长度减少
            rod_length = rod_length % rod_pieces[i].length;
        }

        return value;
    }

    /**
     * 切木块-动态规划
     *
     * @param cut_value
     * @param rod_length
     * @return
     */
    public static int getValueByDP(int[] cut_value, int rod_length) {
        //存储每一个子阶段的最大价值
        int[] rod_value = new int[rod_length];

        //长度为1的木头价值就是其本身
        rod_value[0] = cut_value[0];

        //依次求解之后每个子阶段的最大值
        for (int i = 1; i < rod_length; i++) {
            //因为有可能最大的cut_value < rod_length
            //所以需要判断能不能不切直接卖
            rod_value[i] = cut_value[Math.min(i, cut_value.length - 1)];

            //依次比较
            for (int j = 0; j <= i - j - 1; j++) {
                rod_value[i] = Math.max(
                        rod_value[i],
                        rod_value[j] + rod_value[i - j - 1]
                );
            }
        }

        return rod_value[rod_length - 1];
    }
}

//测试代码
public class RodCutTest {
    public static void main(String[] args) {
        int[] cut_value = {1, 4, 5, 7, 10, 17, 17, 20, 24, 30};
        int maxLength = 20;
        int[][] rod_value = new int[3][maxLength];
        for(int i=0;i<maxLength;i++) {
            rod_value[0][i] = i + 1;
            rod_value[1][i] = RodCut.getValueByDP(cut_value,i+1);
            rod_value[2][i] = RodCut.getValueByGreedy(cut_value,i+1);
        }
        printMatrix(rod_value);
    }

    private static void printMatrix(int[][] A) {
        int m = A.length;
        int n = A[0].length;
        String str = "";
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                str += A[i][j] + "\t";
            }
            str += "\n";
        }
        System.out.println(str);
    }
}

//运行结果
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	
1	4	5	8	10	17	18	21	24	30	31	34	35	38	41	47	48	51	54	60	
1	4	5	8	9	17	18	21	22	30	31	34	35	38	39	47	48	51	52	60

三. 活动选择问题

1.题目描述

2.代码实现

public class Activity implements Comparable<Activity> {
    //编号
    int No;
    //活动开始时间
    int startTime;
    //活动结束时间
    int endTime;

    //构造方法
    public Activity(int no, int startTime, int endTime) {
        No = no;
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(Activity activity) {
        return endTime - activity.endTime;
    }
}

class ActivitySelection {
    /**
     * 活动选择问题-贪心
     * @param activityStartEndTime
     * @return
     */
    public static LinkedList<Integer> selectFrom(int[][] activityStartEndTime){
        //活动的个数
        int n = activityStartEndTime.length;

        //存储每一个活动对应的Activity的集合
        Activity[] activities = new Activity[n];
        //初始化
        for (int i = 0; i < n; i++) {
            activities[i] = new Activity(i + 1, activityStartEndTime[i][0], activityStartEndTime[i][1]);
        }

        //按照活动结束时间从小到大排序
        Arrays.sort(activities);

        //存储选择的活动
        LinkedList<Integer> selectActivities = new LinkedList<>();
        //第一个活动直接加入
        selectActivities.add(activities[0].No);
        //记录之前活动的结束时间
        int previousEndTime = activities[0].endTime;

        //贪心找到所有的活动
        for (int i = 0; i < n; i++) {
            if (activities[i].startTime >= previousEndTime) {
                //添加活动
                selectActivities.add(activities[i].No);

                //更新上一个活动的结束时间
                previousEndTime = activities[i].endTime;
            }
        }

        return selectActivities;
    }
}

//测试代码
public class ActivitySelectionTest {
    public static void main(String[] args) {
        int[][] activityStartEndTime = {{8,14},{9,12},{11,13},{16,19},{14,18},{13,15},{10,21},{20,22},{16,20},{11,16},{13,17}};
        LinkedList<Integer> selectedActivities = ActivitySelection.selectFrom(activityStartEndTime);
        System.out.println(selectedActivities);
    }
}

//运行结果
[2, 6, 4, 8]

四. 最优装载问题

1.题目描述

2.代码实现

public class Container implements Comparable<Container> {
    //集装箱的编号
    int No;
    //集装箱的重量
    int weight;

    //构造方法
    public Container(int no, int weight) {
        No = no;
        this.weight = weight;
    }

    @Override
    public int compareTo(Container container) {
        return weight - container.weight;
    }
}

/**
 * 最优装载问题
 */
class MaxLoading {
    /**
     *
     * @param containers_weight
     * @param capacity
     * @return
     */
    public static LinkedList<Integer> selectFrom(int[] containers_weight, int capacity){
        //集装箱的数量
        int n = containers_weight.length;

        //存储集装箱对应的Container集合
        Container[] containers = new Container[n];
        //初始化
        for (int i = 0; i < n; i++) {
            containers[i] = new Container(i+1, containers_weight[i]);
        }

        //按照集装箱的大小从小到大排序
        Arrays.sort(containers);

        //存储选择的集装箱
        LinkedList<Integer> selectedContainers = new LinkedList<>();

        //贪心找到选择的集装箱
        for (int i = 0; i < n && capacity > 0; i++) {
            //如果还可以装得下
            if (capacity >= containers[i].weight){
                //加入集装箱
                selectedContainers.add(containers[i].No);

                //更新容量
                capacity -= containers[i].weight;
            }
        }

        return selectedContainers;
    }
}

//测试代码
public class MaxLoadingTest {
    public static void main(String[] args) {
        int[] containers_weight = {100,200,50,90,150,50,20,80};
        int capacity = 400;
        LinkedList<Integer> selectedContainers = MaxLoading.selectFrom(containers_weight, capacity);
        System.out.println(selectedContainers);
    }
}

//运行结果
[7, 3, 6, 8, 4, 1]

五. 哈夫曼编码问题

1.题目描述

2.代码实现

public class HuffmanCoding {
    public static HashMap<String,String> getCodes(String[] chars, double[] frequency){
        //优先队列
        PriorityQueue<Node> nodes = new PriorityQueue<>();

        //加入数据
        for (int i = 0; i < chars.length; i++) {
            nodes.add(new Node(chars[i],frequency[i]));
        }

        //构建哈弗曼树
        while (nodes.size() > 1){
            //每一次弹出两个frequency最小的node
            Node left = nodes.poll();
            Node right = nodes.poll();

            //将合成的新的node加入优先队列
            nodes.add(new Node(left,right));
        }

        //输出数据
        HashMap<String,String> huffman_codes = new HashMap<>();
        traverse(nodes.poll(),"",huffman_codes);
        return huffman_codes;
    }

    //递归得到结果
    private static void traverse(Node node, String str, HashMap<String, String> huffman_codes) {
        if (node.leftChild == null){
            huffman_codes.put(node.chr,str);
        }else {
            traverse(node.leftChild,str+"0",huffman_codes);
            traverse(node.rightChild,str+"1",huffman_codes);
        }
    }

    //测试代码
    public static void main(String[] args) {
        String[] chars = {"a","b","c","d","e","f"};
        double[] frequency = {0.45,0.13,0.12,0.16,0.09,0.05};

        HashMap<String, String> codes = getCodes(chars, frequency);
        Set<String> keys = codes.keySet();
        for (String key : keys) {
            System.out.println(key+" "+codes.get(key));
        }
    }
}

//运行结果
a 0
b 101
c 100
d 111
e 1101
f 1100

public class Node implements Comparable<Node>{
    String chr;
    double frequency;
    Node leftChild;
    Node rightChild;

    //叶子节点
    public Node(String chr, double frequency) {
        this.chr = chr;
        this.frequency = frequency;

        leftChild = null;
        rightChild = null;
    }

    //树根节点
    public Node(Node leftChild, Node rightChild) {
        chr = null;
        frequency = leftChild.frequency + rightChild.frequency;

        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

    @Override
    public int compareTo(Node node) {
        if (frequency - node.frequency > 0) return 1;
        else if (frequency - node.frequency < 0) return -1;
        else return 0;
    }
}

时间复杂度：θ(nlogn)

3.贪心的正确性

六. 单源最短路径问题

1.题目描述

使用迪杰斯特拉算法求解，理解参考：迪杰斯特拉（Dijkstra)算法最通俗易懂的讲解

2.代码

public class NodeInAdjacencyList {
    String name;
    int road_length;

    public NodeInAdjacencyList(String name, int road_length) {
        this.name = name;
        this.road_length = road_length;
    }
}

public class NodeWithShortestPath {
    String from;
    String name;
    int route_length;

    public NodeWithShortestPath(String name, String from, int route_length) {
        this.name = name;
        this.from = from;
        this.route_length = route_length;
    }
}

public class NodeWithShortestPathInRankedList extends NodeWithShortestPath {
    NodeWithShortestPathInRankedList previous;
    NodeWithShortestPathInRankedList next;

    public NodeWithShortestPathInRankedList(String node_name, int route_length, String node_from, NodeWithShortestPathInRankedList previous, NodeWithShortestPathInRankedList next) {
        super(node_name, node_from, route_length);
        this.previous = previous;
        this.next = next;
    }

    public void changeRoute(String node_from,int route_length){
        //跟新更短的数据
        this.route_length = route_length;
        this.from = node_from;

        //判断是否需要交换位置
        while (previous != null && route_length < previous.route_length){
            NodeWithShortestPathInRankedList tempPrevious = this.previous.previous;
            if (this.previous.previous.next != null){
                this.previous.previous.next = this;
            }

            if (this.next != null){
                this.next.previous = this.previous;
            }

            //交换数据
            this.previous.previous = this;
            this.previous.next = this.next;
            this.next = this.previous;
            this.previous = tempPrevious;
        }
    }
}

public class Dijkstra {
    /**
     * 迪杰斯特拉算法-求解带权有向图的最短路径问题
     * @param routeGraph
     * @param start
     * @return
     */
    public static LinkedList<NodeWithShortestPath> getByDijkstra(HashMap<String,LinkedList<NodeInAdjacencyList>> routeGraph, String start){
        //存储已决集的结点
        LinkedList<NodeWithShortestPath> shortest_route = new LinkedList<>();

        //模拟优先队列存储未决集的节点
        HashMap<String, NodeWithShortestPathInRankedList> nodes_with_shortest_route = new HashMap<>();

        //模拟存储未决节点集合的头指针
        NodeWithShortestPathInRankedList rankedList = null;
        //模拟存储未决集节点集合的尾指针
        NodeWithShortestPathInRankedList previous = null;

        //遍历所有位置 创建双向循环列表的过程
        for (String node_name : routeGraph.keySet()) {
            //创建未决集的节点
            NodeWithShortestPathInRankedList new_node;

            //如果是第一个节点
            if (node_name.equals(start)){
                //创建第一个节点 前置指针和后置指针都是null
                new_node = new NodeWithShortestPathInRankedList(node_name,0,start,null,null);
                //头指针指向第一个节点
                rankedList = new_node;
            }else {
                //创建新的结点 前置指针指向上一个节点，后置指针是null
                new_node = new NodeWithShortestPathInRankedList(node_name,(int)Integer.MAX_VALUE,"",previous,null);
                //上一个节点的后置指针指向新的结点
                previous.next = new_node;
            }

            //尾指针指向最后的结点
            previous = new_node;

            //存储未决节点，用来下面的遍历
            nodes_with_shortest_route.put(node_name,new_node);
        }

        //只有还有未决集的节点，就继续
        while (rankedList != null){
            //第一个节点直接加入
            shortest_route.add(new NodeWithShortestPath(rankedList.name,rankedList.from, rankedList.route_length));

            //遍历每一个未决集节点 调整位置
            for (NodeInAdjacencyList node : routeGraph.get(rankedList.name)) {
                //如果到达未决集节点的距离有变化，判断是否更小
                if (node.road_length + rankedList.route_length < nodes_with_shortest_route.get(node.name).route_length){
                    //更新数据以及交换位置
                    nodes_with_shortest_route.get(node.name).changeRoute(rankedList.name,node.road_length + rankedList.route_length);
                }
            }

            //未决结点成为已决结点，弹出
            if (rankedList.next != null){
                //即将成为头节点的结点的前置指针置空
                rankedList.next.previous = null;
            }
            //头指针指向新的位置
            rankedList = rankedList.next;
        }

        return shortest_route;
    }

    //测试代码
    public static void main(String[] args) {
        HashMap<String,LinkedList<NodeInAdjacencyList>> routeGraph = new HashMap<>();

        routeGraph.put("A",new LinkedList<NodeInAdjacencyList>());
        routeGraph.get("A").add(new NodeInAdjacencyList("B",2));
        routeGraph.get("A").add(new NodeInAdjacencyList("C",4));

        routeGraph.put("B",new LinkedList<NodeInAdjacencyList>());
        routeGraph.get("B").add(new NodeInAdjacencyList("C",1));
        routeGraph.get("B").add(new NodeInAdjacencyList("D",3));
        routeGraph.get("B").add(new NodeInAdjacencyList("E",2));

        routeGraph.put("C",new LinkedList<NodeInAdjacencyList>());
        routeGraph.get("C").add(new NodeInAdjacencyList("E",3));

        routeGraph.put("D",new LinkedList<NodeInAdjacencyList>());
        routeGraph.get("D").add(new NodeInAdjacencyList("F",2));

        routeGraph.put("E",new LinkedList<NodeInAdjacencyList>());
        routeGraph.get("E").add(new NodeInAdjacencyList("D",3));
        routeGraph.get("E").add(new NodeInAdjacencyList("F",2));

        routeGraph.put("F",new LinkedList<NodeInAdjacencyList>());

        LinkedList<NodeWithShortestPath> shortest_route = getByDijkstra(routeGraph, "A");
        for (NodeWithShortestPath node : shortest_route) {
            System.out.println(node.name+" -（from "+node.from+"）- "+node.route_length);
        }
    }
}

//运行结果
A -（from A）- 0
B -（from A）- 2
C -（from B）- 3
E -（from B）- 4
D -（from B）- 5
F -（from E）- 6

时间复杂度：节点数|V|，连边数|E|，θ(|E|log|V|)

3.贪心的正确性

选择进入已决集的节点的距离一定是最短的。

七. 最小生成树问题

1.问题描述

2.代码

有两种解决该问题的方式：

• Prim（普里姆）算法求解最小生成树-节点贪心算法。
• Kruskal（克鲁斯卡尔）算法求解最小生成树-连边贪心算法。

① 主要的实现类

public class MinSpanningTree {
    /**
     * Prim算法求解最小生成树-节点贪心算法
     * @param graph
     * @return
     */
    public static LinkedList<Edge> getByPrim(HashMap<String, LinkedList<NodeInAdjacencyList>> graph) {
        //存储最终连接的边的信息或者说已决集
        LinkedList<Edge> spanningTree = new LinkedList<>();
        //模拟双向链表的头结点
        NodeWithDistanceInRankedList unsettled = null;
        //存储未决集的节点
        HashMap<String, NodeWithDistanceInRankedList> nodes_with_distance = new HashMap<>();

        //模拟双向链表加入第一个点
        HashSet<String> vertexSet = new HashSet<>(graph.keySet());
        String startVertex = vertexSet.iterator().next();
        NodeWithDistanceInRankedList previous = new NodeWithDistanceInRankedList(startVertex,startVertex,0,null,null);
        nodes_with_distance.put(startVertex,previous);
        unsettled = previous;
        vertexSet.remove(startVertex);

        //依次在双向链表中加入剩余的点
        for (String v : vertexSet) {
            NodeWithDistanceInRankedList newNode = new NodeWithDistanceInRankedList(v, startVertex, Integer.MAX_VALUE, previous, null);
            previous.next = newNode;
            nodes_with_distance.put(v,newNode);
            previous = newNode;
        }

        while (unsettled != null){
            //如果不是第一个点就加入已决集
            if (!unsettled.name.equals(startVertex)){
                spanningTree.add(new Edge(unsettled.name,unsettled.from));
                unsettled.distance = 0;
            }

            //依次判断
            for (NodeInAdjacencyList node : graph.get(unsettled.name)) {
                //如果有更短到达的边
                if (node.road_length < nodes_with_distance.get(node.name).distance){
                    nodes_with_distance.get(node.name).changeDistance(unsettled.name,node.road_length);
                }
            }

            //模拟的头指针后移
            if (unsettled.next != null){
                unsettled.next.previous = null;
            }
            unsettled = unsettled.next;
        }


        return spanningTree;
    }

    /**
     * Kruskal算法求解最小生成树-连边贪心算法
     * @param graph
     * @return
     */
    public static LinkedList<Edge> getByKruskal(HashMap<String, LinkedList<NodeInAdjacencyList>> graph) {
        //存储最终连接的边的信息或者说已决集
        LinkedList<Edge> spanningTree = new LinkedList<>();

        //创建并查集并初始化数据
        Union<String> vertexUnion = new Union<>();
        for (String v : graph.keySet()) {
            vertexUnion.add(v);
        }

        //优先队列
        PriorityQueue<EdgeWithLength> edgePQ = new PriorityQueue<>();
        //存储点
        HashSet<String> edgeStrSet = new HashSet<>();

        //优先队列和边信息的集合数据填充
        for (String v : graph.keySet()) {
            for (NodeInAdjacencyList adjNode : graph.get(v)) {
                //创建这条边的信息
                String edgeStr = new Edge(v, adjNode.name).toString();

                //如果这条边还没有包含进来
                if (!edgeStrSet.contains(edgeStr)){
                    //创建含有边值的边加入优先队列
                    EdgeWithLength e = new EdgeWithLength(v, adjNode.name, adjNode.road_length);
                    edgePQ.add(e);

                    //这条边的信息加入到集合中
                    edgeStrSet.add(edgeStr);
                }
            }
        }

        //依次找到最短的边是所有点都加入到集合中
        while (edgePQ.size() > 0){
            //弹出一个含有边值的边
            EdgeWithLength edge = edgePQ.poll();

            //判断能否加入
            if (!vertexUnion.isSameUnion(edge.firstVertex,edge.secondVertex)){
                //加入
                spanningTree.add(new Edge(edge.firstVertex,edge.secondVertex));

                //并查集 内容更新
                vertexUnion.union(edge.firstVertex,edge.secondVertex);
            }
        }

        return spanningTree;
    }
}

② 辅助类

/**
 * 简单的连边类
 */
public class Edge {
    String firstVertex;
    String secondVertex;

    public Edge(String firstVertex, String secondVertex){
        if (firstVertex.compareTo(secondVertex) > 0){
            this.firstVertex = secondVertex;
            this.secondVertex = firstVertex;
        }else {
            this.firstVertex = firstVertex;
            this.secondVertex = secondVertex;
        }
    }

    @Override
    public String toString() {
        return firstVertex + " --- " + secondVertex;
    }
}

/**
 * 带有边值的连边类
 */
public class EdgeWithLength extends Edge implements Comparable<EdgeWithLength> {
    int length;

    public EdgeWithLength(String firstVertex, String secondVertex) {
        super(firstVertex, secondVertex);
        length = 0;
    }

    public EdgeWithLength(String firstVertex, String secondVertex, int length) {
        super(firstVertex, secondVertex);
        this.length = length;
    }

    @Override
    public int compareTo(EdgeWithLength e) {
        return this.length - e.length;
    }
}

/**
 * 表示图所需的邻接链表中的节点类
 */
public class NodeInAdjacencyList {
    String name;
    int road_length;

    public NodeInAdjacencyList(String name, int road_length) {
        this.name = name;
        this.road_length = road_length;
    }
}

/**
 * 图中的节点类，并标注来源节点和距离，可按照距离排序
 */
public class NodeWithDistanceInRankedList {
    String name;
    String from;
    int distance;

    NodeWithDistanceInRankedList previous;
    NodeWithDistanceInRankedList next;

    public NodeWithDistanceInRankedList(String name, String from, int distance,
                                        NodeWithDistanceInRankedList previous, NodeWithDistanceInRankedList next) {
        this.name = name;
        this.from = from;
        this.distance = distance;
        this.previous = previous;
        this.next = next;
    }

    public void changeDistance(String node_from, int distance) {
        this.distance = distance;
        this.from = node_from;
        while(this.previous != null && distance < this.previous.distance) {
            NodeWithDistanceInRankedList tempPreviousPrevious = this.previous.previous;
            if(this.previous.previous!=null) {
                this.previous.previous.next = this;
            }
            if(this.next!=null) {
                this.next.previous = this.previous;
            }
            this.previous.previous = this;
            this.previous.next = this.next;
            this.next = this.previous;
            this.previous = tempPreviousPrevious;
        }
    }
}

/**
 * 并查集类
 * @param <T>
 */
public class Union<T> {
    HashMap<T,T> unionMap;

    public Union() {
        unionMap = new HashMap<>();
    }

    public void add(T s){
        unionMap.put(s,s);
    }

    public T find(T s){
        while (unionMap.get(s) != s){
            s = unionMap.get(s);
        }

        return s;
    }

    public void union(T s1,T s2){
        T u1 = find(s1);
        T u2 = find(s2);

        if (u1 != u2){
            unionMap.put(u2,u1);
        }
    }

    public boolean isSameUnion(T s1, T s2){
        return find(s1) == find(s2);
    }
}

③ 测试类

public class MinSpanningTreeTest {
    public static void main(String[] args) {
        HashMap<String, LinkedList<NodeInAdjacencyList>> graph =
                new HashMap<String, LinkedList<NodeInAdjacencyList>>();
        graph.put("0", new LinkedList<NodeInAdjacencyList>());
        graph.get("0").add(new NodeInAdjacencyList("1", 25));
        graph.get("0").add(new NodeInAdjacencyList("3", 75));
        graph.get("0").add(new NodeInAdjacencyList("4", 150));
        graph.put("1", new LinkedList<NodeInAdjacencyList>());
        graph.get("1").add(new NodeInAdjacencyList("0", 25));
        graph.get("1").add(new NodeInAdjacencyList("2", 50));
        graph.get("1").add(new NodeInAdjacencyList("5", 150));
        graph.put("2", new LinkedList<NodeInAdjacencyList>());
        graph.get("2").add(new NodeInAdjacencyList("1", 50));
        graph.get("2").add(new NodeInAdjacencyList("5", 120));
        graph.put("3", new LinkedList<NodeInAdjacencyList>());
        graph.get("3").add(new NodeInAdjacencyList("0", 75));
        graph.get("3").add(new NodeInAdjacencyList("4", 100));
        graph.put("4", new LinkedList<NodeInAdjacencyList>());
        graph.get("4").add(new NodeInAdjacencyList("0", 150));
        graph.get("4").add(new NodeInAdjacencyList("3", 100));
        graph.get("4").add(new NodeInAdjacencyList("6", 300));
        graph.get("4").add(new NodeInAdjacencyList("7", 325));
        graph.put("5", new LinkedList<NodeInAdjacencyList>());
        graph.get("5").add(new NodeInAdjacencyList("1", 150));
        graph.get("5").add(new NodeInAdjacencyList("2", 120));
        graph.get("5").add(new NodeInAdjacencyList("8", 200));
        graph.put("6", new LinkedList<NodeInAdjacencyList>());
        graph.get("6").add(new NodeInAdjacencyList("4", 300));
        graph.get("6").add(new NodeInAdjacencyList("7", 100));
        graph.get("6").add(new NodeInAdjacencyList("9", 250));
        graph.put("7", new LinkedList<NodeInAdjacencyList>());
        graph.get("7").add(new NodeInAdjacencyList("4", 325));
        graph.get("7").add(new NodeInAdjacencyList("6", 100));
        graph.get("7").add(new NodeInAdjacencyList("8", 100));
        graph.get("7").add(new NodeInAdjacencyList("10", 400));
        graph.put("8", new LinkedList<NodeInAdjacencyList>());
        graph.get("8").add(new NodeInAdjacencyList("5", 200));
        graph.get("8").add(new NodeInAdjacencyList("7", 100));
        graph.get("8").add(new NodeInAdjacencyList("10", 300));
        graph.put("9", new LinkedList<NodeInAdjacencyList>());
        graph.get("9").add(new NodeInAdjacencyList("6", 250));
        graph.get("9").add(new NodeInAdjacencyList("10", 50));
        graph.put("10", new LinkedList<NodeInAdjacencyList>());
        graph.get("10").add(new NodeInAdjacencyList("7", 400));
        graph.get("10").add(new NodeInAdjacencyList("8", 300));
        graph.get("10").add(new NodeInAdjacencyList("9", 50));


        LinkedList<Edge> edges1 = MinSpanningTree.getByPrim(graph);
        System.out.println("Results from Prim:");
        for(Edge e : edges1) {
            System.out.println(e);
        }

        LinkedList<Edge> edges2 = MinSpanningTree.getByKruskal(graph);
        System.out.println("Results from Kruskal:");
        for(Edge e : edges2) {
            System.out.println(e);
        }
    }
}

//运行结果
Results from Prim:
0 --- 1
1 --- 2
0 --- 3
3 --- 4
2 --- 5
5 --- 8
7 --- 8
6 --- 7
6 --- 9
10 --- 9
Results from Kruskal:
0 --- 1
1 --- 2
10 --- 9
0 --- 3
6 --- 7
3 --- 4
7 --- 8
2 --- 5
5 --- 8
6 --- 9

总结

1.贪心算法特征

① 一个问题可以拆分为若干个子问题。

② 一个问题的最优解一定包含其子问题的最优解。

③ 全局最优解可以由一系列局部最优选解达到（贪心选择性质）。

2.与动态规划异同

不具备贪心选择性质，算法需要考虑当前决策和子问题最优解。