图的最小生成树算法

两个均是贪心算法，均是先找最小边，再找次小边。重点在于如何判断是否形成回路。

Kruskal算法：解决方法，连通分量。O(n+eloge) 邻接表

仅适用于无向图。最小堆找出全局小边。通过检查边两端顶点是否在同一连通分量上来判断是否形成回路，若是，则舍弃，不是，则添加。

而判定连通分量通过并查集实现。如此循环N-1次，或者堆为空，则结束。

为什么Kruskal只适用于无向图？因为并查集判定连通分量是通过等价关系判定的，而有向图连通分量显然不满足等价关系。

上面方法也可以用来判定无向图中是否存在环路。

Prim算法：O(eloge)

有向图，无向图均可。通过是否是割边来判断回路。具体来说，通过一标记数组标记生成树节点，对于每个节点的向外割边，取最小边作为下一生成树边，

并将节点加入标记数组，更新割边，如此反复，直至覆盖所有顶点或者割边堆为空。

prim之所以适用于有向图是因为割边本身就是有向的。

下面给出Java代码：

Java中最小堆就是PriorityQueue.

并查集：

 1 package com.company;
 2 import java.util.ArrayList;
 3 /**
 4  * Created by qiguo on 2017/4/6.
 5  */
 6 public class UnionFindSet {
 7     ArrayList<Integer> arrayList;
 8 
 9     public UnionFindSet(){
10         arrayList = new ArrayList<>(20);
11         for (int i = 0; i < 20; i++) {
12             arrayList.add(-1);
13         }
14     }
15 
16     /**
17      * find the set that element belongs to
18      * @param r element
19      * @return set name
20      */
21     public int find(int r){
22         int root = r;
23         while (arrayList.get(root) > 0){
24             root = arrayList.get(root);
25         }
26         return root;
27     }
28 
29     /**
30      * Union two set, the small set points to the large one
31      * @param r1 set 1
32      * @param r2 set 2
33      */
34     public void union(int r1, int r2){
35         int p1 = find(r1);
36         int p2 = find(r2);
37         if (p1 == p2){
38             return;
39         }
40         if (arrayList.get(p1) <= arrayList.get(p2)){
41             arrayList.set(p1, arrayList.get(p1) + arrayList.get(p2));
42             arrayList.set(p2,p1);
43         }else {
44             arrayList.set(p2, arrayList.get(p1) + arrayList.get(p2));
45             arrayList.set(p1,p2);
46         }
47     }
48 
49 }

图算法：

 public void kruskal(){
        PriorityQueue<Edge> edges = readEdge();
        UnionFindSet ufSet = new UnionFindSet();
        int count = numVertices - 1;
        while (!edges.isEmpty() && count > 0){
            Edge edge = edges.poll();
            if (ufSet.find(edge.v1) != ufSet.find(edge.v2)){
                ufSet.union(edge.v1, edge.v2);
                System.out.printf("(" + edge.v1 + ", " + edge.v2 + ") ");
                count--;
            }
        }
        System.out.println();
    }

    public void prim(){
        HashSet<Integer> resultSet = new HashSet<>();
        int count = 1;
        resultSet.add(0);
        PriorityQueue<Edge> edgePriorityQueue = new PriorityQueue<>();
        for (int i = 0; i < numVertices; i++) {
            if (graph[0][i] > 0 && graph[0][i] < 1000){
                Edge edge = new Edge(0, i, graph[0][i]);
                edgePriorityQueue.add(edge);
            }
        }
        while (!edgePriorityQueue.isEmpty() && count < numVertices){
            Edge tmp = edgePriorityQueue.poll();
            if (resultSet.contains(tmp.v2)){
                continue;
            }else {
                System.out.printf("(" + tmp.v1 + ", " + tmp.v2 + ") ");
                int node;
                if (resultSet.contains(tmp.v1)) {
                    node = tmp.v2;
                } else {
                    node = tmp.v1;
                }
                resultSet.add(node);
                count++;
                for (int i = 0; i < numVertices; i++) {
                    if (graph[node][i] > 0 && graph[node][i] < 1000 && !resultSet.contains(i)){
                        Edge edge = new Edge(node, i, graph[node][i]);
                        edgePriorityQueue.add(edge);
                    }
                }
            }
        }
    }