001什么是最小生成樹算法(Minimum Cost Spanning Tree簡稱 MST)？

所謂生成樹，就是n個點之間連成n-1條邊的圖形。最小生成樹，就是權值（兩點間直線的值）之和的最小值。由此可以總結構造最小生成樹的要求有：（1）必須只使用該圖中的邊來構造最小生成樹；（2）必須使用且僅使用（n-1）條邊來連接圖中的n個頂點；（3）不能使用產生回路的邊；（4）要求樹的（n-1）條邊的權值之和是最小的。

002什么是kruskal算法？

Kruskal（克魯斯卡爾算法）算法是一種用來查找最小生成樹的算法。Kruskal算法是基于貪心的思想得到的。首先我們把所有的邊按照權值先從小到大排列，接著按照順序選取每條邊，如果這條邊的兩個端點不屬于同一集合，那么就將它們合并，直到所有的點都屬于同一個集合為止。換而言之，Kruskal算法就是基于并查集的貪心算法。

003kruskal算法具體實現？

public static class MySets {
    public HashMap<Node, List<Node>> setMap;
    public MySets(List<Node> nodes) {
        for (Node cur : nodes) {
            List<Node> set = new ArrayList<Node>();
            set.add(cur);
            setMap.put(cur, set);
        }
    }
    public boolean isSameSet(Node from, Node to) {
        List<Node> fromSet = setMap.get(from);
        List<Node> toSet = setMap.get(to);

        return fromSet == toSet;
    }
    public void union(Node from, Node to) {
        List<Node> fromSet = setMap.get(from);
        List<Node> toSet = setMap.get(to);

        for (Node toNode : toSet) {
            fromSet.add(toNode);
            setMap.put(toNode, fromSet);
        }
    }
}

004什么是prim算法？

prim算法 (普里姆算法)我們先初始定義一個頂點u，然后在相鄰的所有邊中找到最小權值的邊 e1，將頂點u鏈接到初始點c之外的頂點v,之后將頂點v放到c中，并且一直重復知道完成。

005prim算法的具體實現？

思路
1. 準備一個邊的小根堆隊列priorityQueue、頂點的集合set和要挑選的邊的集合result
2. 遍歷圖的頂點nodes，將隨機的一個頂點node放到集合set里面，將頂點node所相連所相連的邊入隊到小根堆隊列priorityQueue。
3. 彈出隊列里面最小權重的邊，判斷這個邊的to節點的是不是在set集合里面，如果不在，則將to節點放到set里面，并把這條邊存到result里面。再將to頂點所相連所相連的邊入隊到priorityQueue。周而復始依次迭代。
4. 3步驟之后break，跳出循環。

public static Set<Edge> primMST(Graph graph) {
    // 解鎖的邊進入小根堆
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());
    HashSet<Node> set = new HashSet<>();
    Set<Edge> result = new HashSet<>(); // 依次挑選的的邊在result里
    for (Node node : graph.nodes.values()) { // 隨便挑了一個點
        // node 是開始點
        if (!set.contains(node)) {
            set.add(node);
            for (Edge edge : node.edges) { // 由一個點，解鎖所有相連的邊
                 priorityQueue.add(edge);
            }
            while (!priorityQueue.isEmpty()) {
                Edge edge = priorityQueue.poll(); // 彈出解鎖的邊中，最小的邊
                Node toNode = edge.to; // 可能的一個新的點
                if (!set.contains(toNode)) { // 不含有的時候，就是新的點
                    set.add(toNode);
                    result.add(edge);
                    for (Edge nextEdge : toNode.edges) {
                        priorityQueue.add(nextEdge);
                    }
                 }
            }
        }
        break;
    }
    return result;
}