克鲁斯科尔算法（Kruskala） -最小生成树

1. 通过将所有权重排序，依次从小到大，依次取，不能形成回路

public class KruskalaCase {

    public static final int FIN = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verxs = data.length;
        int[][] weight = {
                {0, 12, FIN, FIN, FIN, 16, 14},
                {12, 0, 10, FIN, FIN, 7, FIN},
                {FIN, 10, 0, 3, 5, 6, FIN},
                {FIN, FIN, 3, 0, 4, FIN, FIN},
                {FIN, FIN, 5, 4, 0, 2, 8},
                {16, 7, 6, FIN, 2, 0, 9},
                {14, FIN, FIN, FIN, 8, 9, 0}
        };
        KMinTree kmt = new KMinTree();
        KGraph graph = kmt.createGraph(verxs, data, weight);
        kmt.show(graph);
        List<ENode> eNodes = kmt.toEnodeList(graph);
        Collections.sort(eNodes);
        List<ENode> minTree = kmt.createMinTree(eNodes, graph);
        System.out.println(minTree);

    }
}

class KMinTree {

    public KGraph createGraph(int verxs, char[] data, int[][] weight) {
        KGraph graph = new KGraph(verxs, data, weight);
        return graph;
    }

    public void show(KGraph graph) {
        for (int i = 0; i < graph.weight.length; i++) {
            for (int j = 0; j < graph.weight[0].length; j++) {
                System.out.printf("%13d ", graph.weight[i][j]);
            }
            System.out.println();
            System.out.println();
        }
    }

    public List<ENode> toEnodeList(KGraph graph) {
        List<ENode> eNodes = new ArrayList<>();
        for (int i = 0; i < graph.weight.length; i++) {
            for (int j = i + 1; j < graph.weight[0].length; j++) {

                if (graph.weight[i][j] != KruskalaCase.FIN && graph.weight[i][j] != 0) {
                    ENode node = new ENode(graph.weight[i][j], graph.data[i], graph.data[j]);
                    eNodes.add(node);
                }
            }
        }
        return eNodes;
    }

    public int getPosition(char c, KGraph graph) {

        for (int i = 0; i < graph.data.length; i++) {
            if (graph.data[i] == c) {
                return i;
            }
        }
        return -1;
    }

    public int getEnd(int[] ends, int postion) {
        while (ends[postion] != 0) {
            postion = ends[postion];
        }
        return postion;
    }

    public List<ENode> createMinTree(List<ENode> nodes, KGraph graph) {
        List<ENode> visited = new ArrayList<>();
        Set<Character> vv = new HashSet<>();
        int[] ends = new int[nodes.size()];

        for (int i = 0; i < nodes.size(); i++) {

            int p1 = getPosition(nodes.get(i).start, graph);
            int p2 = getPosition(nodes.get(i).end, graph);

            int m = getEnd(ends, p1);
            int n = getEnd(ends, p2);
            if (m != n) {
                ends[m]  = n;
                visited.add(nodes.get(i));
            }
        }
        return visited;
    }
}

class ENode implements Comparable<ENode> {

    int weight;
    char start;
    char end;

    public ENode(int weight, char start, char end) {
        this.weight = weight;
        this.start = start;
        this.end = end;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("ENode{");
        sb.append("weight=").append(weight);
        sb.append(", start=").append(start);
        sb.append(", end=").append(end);
        sb.append('}');
        return sb.toString();
    }

    @Override
    public int compareTo(ENode o) {
        return this.weight - o.weight;
    }
}

class KGraph {
    int verxs;
    char[] data;
    int[][] weight;
    public KGraph(int verxs, char[] data, int[][] weight) {
        this.verxs = verxs;
        this.data = data;
        this.weight = weight;
    }
}