package cn.codepub.algorithms.graph;

import cn.codepub.algorithms.graph.utils.UnionFindSet;
import org.junit.Test;

import java.util.*;

/**
 * <p>
 * Created with IntelliJ IDEA. 15/12/16 15:39
 * </p>
 * <p>
 * ClassName:Kruskal
 * </p>
 * <p>
 * Description:使用克鲁斯卡尔算法求最小生成树，该算法的核心是一个不相交集，也就是说若加入当前边不形成回路的话即合法，否则不合法
 * 而实现不相交集最常用的方法就是使用并查集，借助于实现的并查集来实现克鲁斯卡尔算法
 * </P>
 *
 * @author Wang Xu
 * @version V1.0.0
 * @since V1.0.0
 */
public class Kruskal {
    /**
     * 实现一个匿名类，提供了基于边的权值的比较器
     */
    public static final Queue<Edge> QUEUE = new PriorityQueue<Edge>(new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            Edge e1 = (Edge) o1;
            Edge e2 = (Edge) o2;
            if (e1.value == e2.value) {
                return 0;
            } else {
                return e1.value > e2.value ? 1 : -1;
            }
        }
    });
    private static List<Vertex> vertexList = new ArrayList<>();//顶点集
    private static List<Edge> visitedEdges = new ArrayList<>();//已访问的边集
    private static List<Edge> edgeList = new ArrayList<>();//边集


    private static class Vertex {
        char name;//顶点名称

        public Vertex(char name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return String.valueOf(name);
        }
    }

    private static class Edge {
        Vertex start;//边的起始点
        Vertex end;//边的终结点
        int value;//边的权值

        public Edge(Vertex a, Vertex b, int val) {
            this.start = a;
            this.end = b;
            this.value = val;
        }

        @Override
        public String toString() {
            return "顶点是：" + this.start.name + "-->" + this.end.name + "，权值：" + this.value;
        }
    }

    /**
     * 添加边的函数
     *
     * @param a   起始点
     * @param b   终结点
     * @param val 边的权值
     */
    public static void addEdge(Vertex a, Vertex b, int val) {
        Edge edge = new Edge(a, b, val);
        edgeList.add(edge);
    }

    public static void minimumSpanningTree() {
        UnionFindSet unionFindSet = new UnionFindSet(vertexList.size());
        // 加入优先级队列
        QUEUE.addAll(edgeList);
        // queue.addAll(edgeList.stream().collect(Collectors.toList()));
        while (!QUEUE.isEmpty()) {
            Edge remove = QUEUE.remove();
            Vertex start = remove.start;//获取起始点
            Vertex end = remove.end;//获取终结点
            int startNo = getVertexNo(vertexList, start.name);//得到起点编号
            int endNo = getVertexNo(vertexList, end.name);//得到终点编号
            int father1 = unionFindSet.findSet(startNo);
            int father2 = unionFindSet.findSet(endNo);
            if (father1 != father2) {//说明两棵树不在同一棵子树
                unionFindSet.union(startNo, endNo);//合并之
                visitedEdges.add(remove);//将当前访问的边加入已访问列表
            }
        }
    }

    private static int getVertexNo(List<Vertex> vertexList, char name) {
        for (int i = 0; i < vertexList.size(); i++) {
            if (vertexList.get(i).name == name) {
                return i;
            }
        }
        return -1;
    }

    @Test
    public void create() {
        //构造图
        Vertex v0 = new Vertex('0');
        Vertex v1 = new Vertex('1');
        Vertex v2 = new Vertex('2');
        Vertex v3 = new Vertex('3');
        Vertex v4 = new Vertex('4');
        vertexList.add(v0);
        vertexList.add(v1);
        vertexList.add(v2);
        vertexList.add(v3);
        vertexList.add(v4);
        addEdge(v0, v1, 2);
        addEdge(v1, v2, 3);
        addEdge(v2, v4, 1);
        addEdge(v0, v4, 4);
        addEdge(v0, v3, 8);
        addEdge(v2, v3, 5);
        addEdge(v4, v3, 7);
        minimumSpanningTree();
        System.out.println("使用克鲁斯卡尔算法选取的边是：");
        System.out.println(visitedEdges);
    }
}

@@ -468,24 +468,94 @@
  Kruskal %7B%0D%0A
+    private static List%3CVertex%3E vertexList = new ArrayList%3C%3E();//%E9%A1%B6%E7%82%B9%E9%9B%86%0D%0A
     /**%0D%0A   
@@ -672,16 +672,22 @@
 mparator
+%3CEdge%3E
 () %7B%0D%0A  
@@ -734,99 +734,27 @@
 are(
-Object o1, Object o2) %7B%0D%0A            Edge e1 = (Edge) o1;%0D%0A            Edge e2 = (Edge) o2;
+Edge e1, Edge e2) %7B
 %0D%0A  
@@ -934,78 +934,8 @@
 );%0D%0A
-    private static List%3CVertex%3E vertexList = new ArrayList%3C%3E();//%E9%A1%B6%E7%82%B9%E9%9B%86%0D%0A
     
@@ -1070,18 +1070,16 @@
 //%E8%BE%B9%E9%9B%86%0D%0A%0D%0A
-%0D%0A
     priv

set jdk to 1.7