克鲁斯卡尔算法(公交站问题)

1. 是什么？

克鲁斯卡尔算法其实也是生成最小生成树的一种算法，和普里姆算法一样，解决同一类问题的。

有7个公交站(A, B, C, D, E, F, G) ，现在需要修路把7个公交站连通，各个公交站之间的距离如下。问如何修路，能使各个公交站连通且修路的总里程数最小？

公交站问题

这个和上次说到的普里姆算法修路问题是一样的，下面来看看用克鲁斯卡尔算法怎么解决。

2. 算法步骤：

• 首先对边的权值进行排序，选择权值最小的一条边，即EF；

• 选择权值第二小的边，即CD；

• 选择权值第三小的边，即DE；

• 选择权值第四小的边，即CE，但是，如果选择CE，那就形成回路了。什么叫回路呢？CDE这个三角形三条边都修了路，那就是回路。所以不能选择CE，那就尝试选择第五小的边，即CF，但是CF也不能选，如果选了，四边形CFED就形成回路了。所以继续选择第六小的边，BF，这个是可以选择的；

• 接下来依次选择EG、AB。7个顶点总共要选择6条边，这6条边分别是：EF、CD、DE、BF、EG、AB。

克鲁斯卡尔算法的难点在于，怎么判断选择了这条边是否会形成回路。

• 判断是否形成回路的方法：记录顶点在最小生成树中的终点，顶点的终点是“在最小生成树中与它连通的最大顶点”。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点终点是否相同，相同就会构成回路。

看了这段话，可能还是一脸蒙逼，还是以上面的图为例，看步骤：

• 首先ABCDEFG这7个顶点，在顶点集合中应该是按照顺序存放的；

• 按照上面的分析，第一次选择的是EF，毫无疑问这一条边的终点是F；

• 第二次选择的CD的终点D；

• 第三次选择的DE，终点是F，因为此时D和E相连，D又和F相连，所以D的终点是F。而且，因为C和D是相连的，D和E相连，E和F也是相连的，所以C的终点此时变成了F。也就是说，当选择了EF、CD、DE这三条边后，C、D、E的终点都是F。当然F的终点也是F，因为F还没和后面的哪个顶点连接。

• 本来接下来应该选择CE的，但是由于C和E的终点都是F，所以就会形成回路。

3. 代码实现：

首先还是定义一个类，用来表示图，如下：

/**
 * 图
 * @author zhu
 *
 */
class Graph{
    List<String> vertexs; // 存放顶点
    int[][] edges; // 邻接矩阵，存放边
    
    public Graph(List<String> vertexs, int[][] edges) {
        this.vertexs = vertexs;
        this.edges = edges;
    }
    
}

然后，再定义一个最小生成树类，写上一些基础方法，比如生成图，打印图的邻接矩阵等，如下：

/**
 * 最小生成树
 * @author zhu
 *
 */
class MinTree{
    
    
    /**
     * 创建图
     * @param vertex 顶点集合
     * @param edges 邻接矩阵
     */
    public Graph createGraph(List<String> vertex, int[][] edges) {
        return new Graph(vertex, edges);
    }
    
    /**
     * 打印图的二维数组
     * @param graph
     */
    public void printGraph(Graph graph) {
        int[][] edges = graph.edges;
        for (int i=0; i<edges.length; i++) {
            System.out.println(Arrays.toString(edges[i]));
        }
    }
}

因为我们上面的分析说了，要对边进行排序。现在边是保存在邻接矩阵中的，不太好处理，所以再定义一个类，用来表示边：

/**
 * 边的对象
 * @author zhu
 *
 */
class EdgeObject{
    String start; // 边的端点
    String end; // 边的另一个端点
    int weight; // 边的权值
    
    public EdgeObject(String start, String end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EdgeObject [start=" + start + ", end=" + end + ", weight=" + weight + "]";
    }
}

有了这个类来表示边，接下来就可以写一个方法，将图的邻接矩阵转成边对象，即在MinTree类中加如下方法：

/**
* 将图的边，即邻接矩阵，转成边对象
* @param graph
* @return
*/
public List<EdgeObject> transfer2Object(Graph graph){
    List<EdgeObject> edgeList = new ArrayList<>();
    for (int i=0; i<graph.edges.length; i++) {
        for (int j=i+1; j<graph.edges[0].length; j++) {
            if (graph.edges[i][j] != 100) {
                EdgeObject edgeObject = new EdgeObject(graph.vertexs.get(i), graph.vertexs.get(j), graph.edges[i][j]);
                edgeList.add(edgeObject);
            }
        }
    }
    return edgeList;
}

获取到了边对象的集合，就可以对其进行排序了，所以中MinTree类中增加一个排序的方法：

/**
* 对边进行排序
* @param edgeObject
*/
public void sortEdges(List<EdgeObject> edgeObjects) {
    Collections.sort(edgeObjects, new Comparator<EdgeObject>() {
        @Override
        public int compare(EdgeObject o1, EdgeObject o2) {
            return o1.weight - o2.weight;
        }
    });
}

至此，对边进行排序的准备工作就做完了。接下来还需要中MinTree类中新增两个方法，即实现克鲁斯卡尔算法的方法，如下：

/**
* 获取索引为i的顶点的终点
* @param endArray 存放终点的数组
* @param i 传入顶点的索引
* @return 顶点i的终点对应的索引
*/
public int getEnd(int[] endArray, int i) {
    while (endArray[i] != 0) {
        i = endArray[i];
    }
    return i;
}
    
/**
* 克鲁斯卡尔算法创建最小生成树
* @param graph 图
* @param currentVertex 开始处理的顶点
*/
public List<EdgeObject> kruskal(Graph graph) {
    // 最终选择的边的集合
    List<EdgeObject> resultList = new ArrayList<>();
    // 用于保存终点的数组
    int[] ends = new int[graph.vertexs.size()];
    // 将图的邻接矩阵转成边对象集合
    List<EdgeObject> list = transfer2Object(graph);
    // 对边进行排序
    sortEdges(list);
    // 遍历边的集合
    for (EdgeObject e : list) {
        int p1 = graph.vertexs.indexOf(e.start); // 边的第一个顶点的索引
        int p2 = graph.vertexs.indexOf(e.end); // 边的第二个顶点的索引
        int m = getEnd(ends, p1); // 获取p1的终点
        int n = getEnd(ends, p2); // 获取p2的终点
        if (m != n) { // 如果这两个顶点的终点相同，就会构成回路，反之就可以添加这条边
            ends[m] = n; // 将索引为m的顶点的终点设置为索引为n的顶点
            resultList.add(e); // 将这条边加入到保存结果的集合中
        }
    }
    return resultList;
}

解释一下这两个方法，首先看第二个方法：

• 首先定义保存最终结果的集合；

• 然后定一个了一个数组，用来保存终点。数组的大小就是图的顶点的个数。下标表示的是顶点，比如下标0，那代表的就是A这个顶点，下标1代表的就是B这个顶点；下标对应的值表示的是该下标对应的顶点的终点的索引。比如ends[0] = 1，表示的是A的终点是B。

• 再然后调用上面的方法，将邻接矩阵转成边对象的集合，并且进行排序；

• 接着遍历这个边的集合，每拿到一条边，就判断这条边的两个端点的终点是否相同。比如第一次拿到的边是EF，那么p1 = 4, p2 = 5。接下来用getEnd方法去获取终点。获取p1终点的时候，保存终点的ends数组中还全部都是0，所以ends[p1] = 0，不进入while循环，直接return了p1的值，即m = 4；同理n = 5。m不等于n，这时，就让ends[4] = 5，4对应的是E，5对应的是F，这句话的作用就是将E的终点设置为了F。

• 拿到的第二条边应该是CD，p1 = 2, p2 = 3，m = 2, n = 3，ends[2] = 3，将C的终点设置成了D。

• 拿到的第三条边是DE，p1 = 3, p2 = 4，因为ends[3]、ends[4] = 0，不会进入while循环，所以m = 3, n = 4，ends[3] = 4，将D的终点设置成了E。

• 拿到的第四条边是CE，p1 = 2, p2 = 4，此时，ends[2] = 3 != 0，所以进入while循环，ends[3] = 4 != 0, ends[4] = 5 != 0, ends[5] = 0，所以m = 5，也就是说，C的终点是索引5对应的，即F；接着看n等于多少。ends[4] = 5 != 0，进入while循环，ends[5] = 0，所以n = 5，此时m和n相等，说明终点是同一个，都是F，所以不添加这条边。

……

这里就是getEnd这个方法不太好理解，调试一下就很清晰了。