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

/**
 * 图
 * @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 + "]";
    }
}

/**
* 将图的边，即邻接矩阵，转成边对象
* @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;
}

/**
* 对边进行排序
* @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;
        }
    });
}

/**
* 获取索引为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;
}