分治

分治(divide and conquer),可以理解为分而治之，就是把一个大问题简化成小问题来解决。
像之前的快速排序、归并排序、二分查找，都是使用了分治的思想的。

二分查找(非递归实现)

这里先实现一个之前没实现过的关于分治的算法就是非递归实现二分查找。
这里代码比较简单就直接贴在这里。

/**
 * 二分查找非递归实现
 * @param arr 带查找的数组，升序
 * @param target 需要查的树
 * @return 返回对应的下标，-1表示没有找到
 */
public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

分治实现汉诺塔问题

问题提出

汉诺塔是一个经典的问题，以下题目粘贴自百度百科：

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上

思想

这个问题就是典型的可以使用分治解决的问题。
而难点在于怎么分化问题，使问题变小。

1. 如果只有一个盘子，问题就很简单了，直接把A杆上的盘1移动到C杆上就好了
2. 如果有两个盘子，问题也不难，借助B杆也可以将两个盘子移动到C杆上
3. 但是如果盘子再增加，问题就会复杂起来了

这里就用分治的思想将多个盘子的问题转化为少盘子的问题，将第二个以上的所有盘子看成一个整体，这样就只有两个盘子了，只需要将上面的整体移动到B杆上，然后将最后的盘子移动到C杆上，最后再将上面的整体从B杆上移动到C盘上就可以了。
然而具体怎么将上面的整体移动到B或者是C，这其实又是一个汉诺塔问题了，再将其分为两个整体就可以了。

整理一下：

1. 只有一个盘子，直接移动就好了
2. 两个以上的盘子
3. 将除最后一个盘子看为一个整体移动到B(借助C)
4. 将最后一个盘子移动到C
5. 将在B上的整体盘子移动到C(借助A)

代码展示

public static void main(String[] args) {
    hanoiTower(5, 'A', 'B', 'C');
}
public static void hanoiTower(int num, char a, char b, char c) {
    // 如果只有一个盘
    if(num == 1) {
        System.out.println("第1个盘从 " + a + "->" + c);
    } else {
        // 看成两个盘，最下面的一个盘和上面的一个盘
        // 1. 把上面所有盘A->B, 中间会利用c
        hanoiTower(num - 1, a, c, b);
        // 2. 最下面的盘移动到c
        System.out.println("第" + num + "个盘从 " + a + "->" + c);
        // 3. 把B塔的所有盘移动到c
        hanoiTower(num - 1, b, a, c);
    }
}

动态规划

介绍

动态规划(Dynamic Programming):的主要思想也是将一个大问题分解成若干个小问题，然后求解从而得到整体的解。
他和分治的区别就是，分治得到的每个小问题是相对统一的。而动态规划后面的问题会需要前面分解成的问题的解来求解。

动态规划解决背包问题

*这里的背包指的是01背包，是不可以重复装商品的。

问题

有若干商品，你拥有一个背包，背包会有背重的上限，而商品会有重量和价格，根据背包的背重上限不同，如何装入价格总量更高的商品。

题目
商品表

商品	重量	价格
吉他(G)	1	1500
音响(S)	4	3000
电脑(L)	3	2000

背包的背重上限是4

分析

物品	0	1	2	3	4
	0	0	0	0	0
吉他(G)	0	1500(G)	1500(G)	1500(G)	1500(G)
音响(S)	0	1500(G)	1500(G)	1500(G)	3000(S)
电脑(L)	0	1500(G)	1500(G)	2000(L)	4500(G+L)

设商品重量为w[] 价格为 val[]
整体表格用v[][] 表示
i 表示每一行，j 表示每一列

如果当前物品重量大于背包重量就直接使用上方的值，也就是上次最优解。
如果小于背包重量，则比较上次最优解和当前物品+放入当前物品后剩余的重量对应的上层最优解谁大，谁更优就用谁。

算法公式：

1. 首先v中的第一行第一列全部置零v[i][0] = 0 v[0][j] = 0
2. 如果w[i] > j 则将v[i][j] = v[i - 1][j]
3. 如果w[i] <= j 则v[i][j] = max(v[i - 1][j], val[i] + v[i - 1][j - w[i]])

实现代码

这里的循环中是从1开始的所以比公式中要多加1，具体看代码。
这里打印结果的方式比较巧妙，因为我们就算得到了规划表也不能得出结果是放入了什么物品。
这里是定义了一个新的二维数组path来存放放入的物品
只要满足v[i-1][j] < val[i - 1] + v[i - 1][j - w[i-1]]就将这时候的ji在path中置为1
最后倒叙遍历path输出为1的i值(就是物品的序号)
j -= w[i - 1];j的步长必须是w[i - 1]因为输出过一个重量为w[i - 1]的物品了下面只能输出余下重量的最优物品解

public static void main(String[] args) {
    int[] w = {1, 4, 3}; // 物品的重量
    int[] val = {1500, 3000, 2000}; // 物品的价值
    int m = 4; // 背包的重量
    int n = val.length; // 物品的个数
    // 记录放的物品
    int[][] path = new int[n + 1][m + 1];
    // 创建二维数组，表
    int[][] v = new int[n + 1][m + 1];
    // 根据前面得到的公式来动态规划处理

    for (int i = 1; i < v.length; i++) {
        for (int j = 1; j < v[i].length; j++) {
            if (w[i - 1] > j) { // 因为程序是从1开始的
                v[i][j] = v[i-1][j];
            } else {
                if (v[i-1][j] < val[i - 1] + v[i - 1][j - w[i-1]]) {
                    v[i][j] = val[i - 1] + v[i - 1][j - w[i-1]];
                    path[i][j] = 1;
                } else {
                    v[i][j] = v[i-1][j];
                }
            }
        }
    }
    int i = path.length - 1;
    int j = path[0].length - 1;
    while (i > 0 && j > 0) {
        if (path[i][j] == 1) {
            System.out.printf("第%d个商品放入到背包\n", i);
            j -= w[i - 1];
        }
        i--;
    }
}

KMP算法

KMP是一种字符串匹配算法，由由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，名称取自三人的名字中的字母。

KMP算法的关键是部分匹配表(Partial Match Table)简称为PMT，如何理解到PMT是如何产生的如何使用的是理解KMP算法的关键。

思想分析

首先就是PMT是什么，这里设原串为"ABABABABABABABABABAC"而模式串为"ABABAC"，这里的PMT就是关于模式串的一个数组我们称之为Next数组

要想理解这个PMT要先了解两个新的概念前缀和后缀，这里直接举例子。
上面设的"ABABAC"的前缀可以是"A"，"AB"，"ABA"，"ABAB"，"ABABA"
后缀可以是"C"，"AC"，"BAC"，"ABAC"，"BABAC"
而部分匹配值就是前缀和后缀相同的最大长度。这里的"ABABAC"的部分匹配值显然是0。注意这里说的是部分匹配值，而不是PMT。

而部分匹配表的每个属性代表的就是模式串中的从0到当前索引的字符串代表的部分匹配值，像A的部分匹配值为0，AB也是0，ABA的就是1，ABAB的就是2等等。

了解了PMT是什么东西后，我们来看这个PMT怎么使用。
在原先的暴力匹配思想中我们失配了后需要完全回溯再重新匹配，比如上述例子中的模式串匹配到C后和原串中的B不同就使失配了，这里原串是要回溯到这次开始的位置+1的位置，模式串需要回溯到开始的位置。
而有了PMT后我们的回溯就不需要这么麻烦，原串不用回溯，模式串回溯到当前失配的元素的索引-1所对应的PMT中的值对应的索引就可以了。

通过上图可以发现，开始的图匹配到B和C的时候失配了，所以根据之前介绍的方案进行回溯。看当前索引的前一个在PMT中对应的值，这里C前面的A对应的部分匹配值为3所以我们的模板串要回溯到3的位置，也就是第4个元素B，再开始和原串开始匹配。

算法分析

分析完思想后，更重要的是怎么实现代码，也就是我们的算法怎么实现。

首先是怎么求出PMT，也就是Next数组。

定义两个累加变量i和j，i代表匹配模板串的索引，j代表求出的PMT中的的值

1. i = 0 时 j = 0 ， 故可以从i = 1开始循环
2. 如果两个索引对应的字符不相等，就需要进行对j进行回溯，直到j<=0或者索引相等
   1. 如果j>0，j就必须回溯到PMT中的j-1时的值
3. 如果两个索引对应的字符相等两变量同时累加1

然后分析KMP的算法

还是定义两个累加变量i和j，i代表原串索引，j代表模板串索引。

1. 对比两个索引对应的字符
2. 不相等就对j进行回溯直到j<=0或者两个索引对应的字符相等
   1. 回溯到PMT中索引j-1对应的值
3. 相等就同时累加
4. 如果j和模板串的长度相等了就代表找到了，返回i - j + 1(细品)
5. 没找到返回-1

代码

求next

public static int[] kmpNext(String dest) {
    // 创建一个next数组保存部分匹配值
    int[] next = new int[dest.length()];
    next[0] = 0; // 如果字符串是长度为1 部分匹配值就是0
    for (int i = 1, j = 0; i < dest.length(); i++) {
        // dest.charAt(i) != dest.charAt(j)
        // 我们需要从next[j-1]获取新的j，.
        // 直到我们发现有dest.charAt(i) == dest.charAt(j)成立时退出
        while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
            j = next[j - 1];
        }
        // dest.charAt(i) == dest.charAt(j)这个条件满足时，部分匹配值就是要加1
        if (dest.charAt(i) == dest.charAt(j)) {
            j++;
        }
        next[i] = j;
    }

    return next;
}

KMP查找

// 写出我们的kmp搜索算法
public static int kmpSearch(String str1, String str2, int[] next) {
    for (int i = 0, j = 0; i < str1.length(); i++) {
        while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
            j = next[j - 1];
        }

        if (str1.charAt(i) == str2.charAt(j)) {
            j++;
        }
        if (j == str2.length()) {
            return i - j + 1;
        }
    }

    return -1;
}

贪婪算法

贪婪算法也可以叫贪心算法，它是指在求解一个问题的时候，每一个步骤都采取最优或者最有利的方案，来希望得到最优的解法，的算法。

贪婪算法得到的解不一定是最优解(有时候会是最优解)，但是这个解是相对接近或者是相对优的解。

问题提出

集合覆盖问题
给出以下城市的集合，要求尽量选取最少的集合来包括所有的城市。

集合	包括城市
K1	北京，上海，天津
K2	广州，北京，深圳
K3	成都，青岛，杭州
K4	天津，上海
K5	杭州，大连

问题分析

这里先考虑使用穷举实现，设集合有n个那么组合就有$2^n - 1$个，看过复杂度的都应该知道幂次级可谓是非常恐怖的，如果这个n为32那么就有大概42亿种组合。显然暴力破解是不可取的。

使用贪婪算法来求解

1. 首先将所有包括的城市找出来加入一个集合记为allAreas
2. 找出所有的集合和allAreas求交集，长度最大的记为maxKey
3. 选取maxKey代表的集合，然后将这个集合中的城市从allAreas移除
4. 重复2-3直到allAreas中无城市及求解完毕

代码实现

准备工作

使用HashMap key存储集合名称，value存储城市集合

// 创建广播电台，放入到Map
HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
// 将电台放入到broadcasts中去
HashSet<String> set1 = new HashSet<>();
set1.add("北京");
set1.add("上海");
set1.add("天津");
HashSet<String> set2 = new HashSet<>();
set2.add("广州");
set2.add("北京");
set2.add("深圳");
HashSet<String> set3 = new HashSet<>();
set3.add("成都");
set3.add("青岛");
set3.add("杭州");
HashSet<String> set4 = new HashSet<>();
set4.add("天津");
set4.add("上海");
HashSet<String> set5 = new HashSet<>();
set5.add("杭州");
set5.add("大连");
broadcasts.put("K1", set1);
broadcasts.put("K2", set2);
broadcasts.put("K3", set3);
broadcasts.put("K4", set4);
broadcasts.put("K5", set5);

算法实现

public static void main(String[] args) {
    // allAreas存放所有地区
    HashSet<String> allAreas = new HashSet<>();
    for (Map.Entry<String, HashSet<String>> entry : broadcasts.entrySet()) {
        allAreas.addAll(entry.getValue());
    }
    // 创建一个ArrayList存放选择的电台集合
    ArrayList<String> selects = new ArrayList<>();
    HashSet<String> tempSet = new HashSet<>();
    // 定义maxKey
    String maxKey;
    int maxCount;
    while (allAreas.size() != 0) {
        maxKey = null;
        maxCount = 0;
        // 遍历broadcasts，取出对应的key
        for (String key : broadcasts.keySet()) {
            // 每进行一次for
            tempSet.clear();

            HashSet<String> areas = broadcasts.get(key);
            tempSet.addAll(areas);
            // 求出tempSet和allAreas集合的交集，交集会赋给tempSet
            tempSet.retainAll(allAreas);

            // 如何当前这个集合包含的未覆盖的地区的数量，比maxKey指向的集合未覆盖的地区还多
            // 就需要重置maxKey
            if (tempSet.size() > 0 &&
                    (maxKey == null || tempSet.size() > maxCount)) {
                maxKey = key;
                maxCount = tempSet.size();
            }
        }
        // maxKey != null 加入select
        if (maxKey != null) {
            selects.add(maxKey);

            allAreas.removeAll(broadcasts.get(maxKey));
        }
    }

    System.out.println(selects);

}

普利姆算法(Prim)

普利姆算法是图论中用来求加权图中的最小生成树(MST)的算法。

最小生成树，指的是给定一个带权无向图，选取一个生成树使得所有边上的权值总和最小。
最小生成树性质：

1. 有n个顶点必有n-1条边
2. 必须包含所有顶点
3. 所有的边都在图中

求最小生成树的算法主要有：普利姆算法和克鲁斯卡尔算法

修路问题

图中有ABCDEFG7个地区，中间的连线代表距离，问如何修一条路链接所有的地区并且路程最短。

这个问题的实质就是一个最小生成树问题。

分析

思路分析

1. 从顶点<A>开始，找出距离<A>路径最短的且没有被访问的顶点并加入<A，G>
2. 从<A，G>开始，找出距离<A，G>路径最短的且没有被访问的顶点并加入<A，G，B>
3. 从<A，G，B>开始，找出距离<A，G，B>路径最短的且没有被访问的顶点并加入<A，G，B，E>
   继续执行直到全部访问完毕

算法分析

因为图在存储的时候是使用顶点集合和一个邻接矩阵实现的，我们需要同过已经访问过的顶点来找和已经访问顶点链接的顶点的最小权值边。这就意味着我们找一个边就需要遍历一次邻接矩阵。

1. 根据最小生成树的性质n个节点有n-1个边，以下步骤执行n-1次，n为节点
2. 遍历邻接矩阵，找到已访问节点中和未访问节点中的最小权值边，并标记二阶矩阵的位置
3. 将找的的节点置为已访问
4. 打印这条边链接的两个顶点(也就是选择这条路修)

代码实现

图的创建代码

这里我们以上面提出的问题为例来创建图
这里用了10000来表示没有路可以链接

public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int verx = data.length;
        // 把邻接矩阵的关系使用二维数组表示
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000}
        };

        // 创建一个Graph对象
        MGraph mGraph = new MGraph(verx);
        // 创建一个MinTree
        MinTree minTree = new MinTree();
        minTree.createGraph(mGraph, verx, data, weight);
    }
}

class MinTree {
    // 创建图的邻接矩阵
    /**
     * 创建图
     * @param graph 图对象
     * @param verxs 图顶点个数
     * @param data 顶点的值
     * @param weight 图的邻接矩阵
     */
    public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
        for (int i = 0; i < verxs; i++) { // 顶点
            graph.data[i] = data[i];

            for (int j = 0; j < verxs; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }
    // 显示图的方法
    public void showGraph(MGraph graph) {
        for (int[] i : graph.weight) {
            System.out.println(Arrays.toString(i));
        }
    }
}
class MGraph {
    int verx; // 表示图的节点个数
    char[] data; // 保存节点数据
    int[][] weight; // 存放边，就是我们的邻接矩阵

    public MGraph(int verx) {
        this.verx = verx;
        data = new char[verx];
        weight = new int[verx][verx];
    }
}

编写生成最小生成树的代码(Prim)

这里的最外面的循环指的就是算法分析中的第一步
而里面的双重循环指的就是遍历邻接矩阵找出最小权值边了

public void prim(MGraph graph, int v) {
    // 表示标记节点(顶点)是否被访问过
    int[] visited = new int[graph.verx];
    // 把当前这个节点标记为已访问
    visited[v] = 1;
    // h1和h2
    int h1 = -1;
    int h2 = -1;
    int minWeight = 10000; // 将其初始化为一个较大的数
    for (int k = 1; k < graph.verx; k++) {
        // 确定每一次生成的子图，和哪个节点的距离最近
        for (int i = 0; i < graph.verx; i++) {
            for (int j = 0; j < graph.verx; j++) {
                if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
                    minWeight = graph.weight[i][j];
                    h1 = i;
                    h2 = j;
                }
            }
        }
        // 找到了一条边是最小的
        System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值：" + minWeight);
        // 将当前的这个节点标记为已经访问
        visited[h2] = 1;
        minWeight = 10000;
    }
}

克鲁斯卡尔算法(Kruskal)

和之前的普利姆算法一样，克鲁斯卡尔算法也是求最小生成树的算法。但是其总体思想却和普利姆算法大有不同。

修路问题2

这里的修路问题2和之前还是一个问题就是把图换了。

和之前一样图中有ABCDEFG7个地区，中间的连线代表距离，问如何修一条路链接所有的地区并且路程最短。

思想分析

1. 首先找出所有的边，并按照其权值进行排序。
2. 根据最小生成树有n-1条边的思想，从权值小到大选择边
3. 如果选取该边后局部最小生成树构成回路则不能选取该边

回路：
首先根据思想我们要选择<F,E>这条边，然后是<C,D>，接着是<D,E>，再之后就是<C,D>注意这里选择CD这条边就会产生回路，也就是CDE三条边连在了一起。

如何判断是否生成回路呢？，这里引出一个新的概念终点，如果两个顶点的终点相同则他们连接比将产生回路。

终点指的是在已连接的最小生成树上每一个顶点的终点都是这颗最小生成树中的最大的顶点。这里的大指的是在顶点集合中的位置前后。
根据图中已经链接上的最小生成树<F,E,D,C>他们4个的终点都是F，所以我们想要链接<C,E>的话是不可以的，因为他们的终点都是F连接在一起必将产生一个回路。
注意：未加入局部最小生成树的终点可以认为是它自身

代码实现

图的创建

这里的代码都是老生常谈了，不介绍了。

public class KruskalCase {

    private int edgeNum; // 边的个数
    private char[] vertexs; // 顶点数组
    private int[][] matrix; // 邻接矩阵
    private static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int matrix[][] = {
                {0, 12, INF, INF, INF, 16, 14},
                {12, 0, 10, INF, INF, 7, INF},
                {INF, 10, 0, 3, 5, 6, INF},
                {INF, INF, 3, 0, 4, INF, INF},
                {INF, INF, 5, 4, 0, 2, 8},
                {16, 7, 6, INF, 2, 0, 9},
                {14, INF, INF, INF, 8, 9, 0}
        };
        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
    }

    public KruskalCase(char[] vertexs, int[][] matrix) {
        int vlen = vertexs.length;
        // 初始化顶点
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexs[i];
        }
        // 初始化边
        this.matrix = new int[vlen][vlen];
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; j++) {
                this.matrix[i][j] = matrix[i][j];
            }
        }

        // 统计边
        for (int i = 0; i < vlen; i++) {
            for (int j = i + 1; j < vlen; j++) {
                if (this.matrix[i][j] != INF) {
                    this.edgeNum++;
                }
            }
        }
    }
}

边类的创建和辅助方法

根据第一条思想，我们需要找出所有的边然后进行排序，则例先创建一个边的类，用来存储所有的边。

class EData {
    char start; // 边的起点
    char end; // 边的终点
    int weight; // 边的权值
    // 构造器
    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
    @Override
    public String toString() {
        return "EData{" +
                "<" + start +
                ", " + end +
                "> weight=" + weight +
                '}';
    }
}

统计边的方法，返回一个存放所有边的数组

private EData[] getEdges() {
    int index = 0;
    EData[] eData = new EData[edgeNum];

    for (int i = 0; i < vertexs.length; i++) {
        for (int j = i + 1; j < vertexs.length; j++) {
            if (matrix[i][j] != INF) {
                eData[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
            }
        }
    }

    return eData;
}

给边排序方法，这里是使用的插入排序，觉得冒泡和选择太慢，高级算法太长，就选用了初级里面的最好的

private void sortEdges(EData[] data) {
    int j;
    for (int i = 1; i < data.length; i++) {
        EData temp = data[i];
        for (j = i; j > 0 && temp.weight < data[j - 1].weight; j--) {
            data[j] = data[j - 1];
        }
        data[j] = temp;
    }
}

还需要一个给定顶点字符就可以找到在顶点数组中该顶点下标的方法

private int getPosition(char ch) {
    for (int i = 0; i < vertexs.length; i++) {
        if (vertexs[i] == ch) { // 找到
            return i;
        }
    }
    return -1;
}

最终方法的实现

这里有两个方法一个是最终的方法，还有一个是获取下标为i的顶点的终点的方法。这里的方式特别精妙，这里一言两语说不清楚，以后有机会会单独写一篇文章解析这里的奥妙

public void kruskal() {
    int index = 0; // 表示最后结果数组的索引
    int[] ends = new int[edgeNum]; // 用于保存已有最小生成树中的每一个顶点在最小生成树中的终点
    // 创建结果数组
    EData[] rets = new EData[vertexs.length - 1];

    // 获取图中 所有的边的集合
    EData[] edges = getEdges();
    // 排序
    sortEdges(edges);

    // 遍历edges数组
    for (int i = 0; i < edgeNum; i++) {
        // 获取到第i条边的第一个顶点和第二个顶点
        int p1 = getPosition(edges[i].start);
        int p2 = getPosition(edges[i].end);
        // 获取p1这个顶点的在已有的最小生成树中的终点
        int m = getEnd(ends, p1);
        int n = getEnd(ends, p2);
        // 判断是否构成回路
        if (m != n) { // 不构成回路
            ends[m] = n; // 设置m在已有最小生成树的中的终点
            rets[index++] = edges[i];
        }
    }

    for (int i = 0; i < rets.length; i++) {
        System.out.println(rets[i]);
    }
}

// 获取下标为i的顶点的终点
private int getEnd(int[] ends, int i) {
    while (ends[i] != 0) {
        i = ends[i];
    }
    return i;
}

Q.E.D.