Kruskal算法

Kruskal算法是图论中用于求解最小生成树的算法，算法时间复杂度为O(eloge) 比较起Prim算法，Kruskal算法虽然同求最小生成树，却更适合稀疏网。

这里图的储存结构建议采用边集数组。 为了提高查找最短边的速度，可以先对边集数组按边上的权值排序。

定义边集数组结点类

public class EdgeArrayNode { private int from; private int to; private int weight; public EdgeArrayNode(int from, int to, int weight) { super(); this.from = from; this.to = to; this.weight = weight; } public int getFrom() { return from; } public void setFrom(int from) { this.from = from; } public int getTo() { return to; } public void setTo(int to) { this.to = to; } public int getWeight() { return weight; } public void setWeight(int weight) { this.weight = weight; } }

定义边集数组结构

其中kruskal()方法就是算法的实现

public class EdgeArray<T> { /** * 顶点个数 */ protected int vertices_num; /** * 边个数 */ protected int edge_num; /** * 图结点 */ protected T[] vertices; /** * 边集数组 */ protected EdgeArrayNode[] edgeArray; public void kruskal() { int vertex1_root, vertex2_root; //定义parent数组 int parent[] = new int[vertices_num]; //初始化parent数组 for (int i = 0; i < vertices_num; i++) { parent[i] = -1; } //依次考察每一条边 for (int i = 0, num = 0; i < edge_num; i++) { EdgeArrayNode node = edgeArray[i]; vertex1_root = findRoot(parent, node.getFrom()); vertex2_root = findRoot(parent, node.getTo()); //位于不同连通分量 if (vertex1_root != vertex2_root) { System.out.println("生成树第" + (num+1) + "条边：" + vertices[node.getFrom()] + "--" + vertices[node.getTo()] + " : " + node.getWeight()); parent[vertex2_root] = vertex1_root; num++; } } } /** * 求vertex_index的根 * @param parent * @param vertex_index * @return */ private int findRoot(int[] parent, int vertex_index) { int root = vertex_index; while (parent[root] > -1) { root = parent[root]; } return root; } }

测试

public class EdgeArrayTester { public static void main(String[] args) { EdgeArray<String> array = new EdgeArray<>(); EdgeArrayNode node0 = new EdgeArrayNode(1, 4, 12); EdgeArrayNode node1 = new EdgeArrayNode(2, 3, 17); EdgeArrayNode node2 = new EdgeArrayNode(0, 5, 19); EdgeArrayNode node3 = new EdgeArrayNode(2, 5, 25); EdgeArrayNode node4 = new EdgeArrayNode(3, 5, 25); EdgeArrayNode node5 = new EdgeArrayNode(4, 5, 26); EdgeArrayNode node6 = new EdgeArrayNode(0, 1, 34); EdgeArrayNode node7 = new EdgeArrayNode(3, 4, 38); EdgeArrayNode node8 = new EdgeArrayNode(0, 2, 46); EdgeArrayNode[] nodeList = {node0, node1, node2, node3, node4, node5, node6, node7, node8}; String[] vertices = {"v0", "v1", "v2", "v3", "v4", "v5"}; int edge_num = 9; int vertices_num = 6; array.vertices_num = vertices_num; array.edge_num = edge_num; array.vertices = vertices; array.edgeArray = nodeList; array.kruskal(); } }

测试结果

生成树第1条边：v1--v4 : 12 生成树第2条边：v2--v3 : 17 生成树第3条边：v0--v5 : 19 生成树第4条边：v2--v5 : 25 生成树第5条边：v4--v5 : 26

结果分析

完整的网图： （1）初始化 得到 {v0}, {v1}, {v2}, {v3}, {v4}, {v5} （2）加入最短边 {v1, v4} 得到 {v0}, {v1, v4}, {v2}, {v3}, {v5}

（3）加入最短边 {v2, v3} 得到 {v0}, {v1, v4}, {v2, v3}, {v5}

（4）加入最短边 {v0, v5} 得到 {v0, v5}, {v1, v4}, {v2, v3}

（5）加入最短边 {v2, v5} 得到 {v0, v5, v2, v3}, {v1, v4}

（6）加入最短边 {v4, v5} 得到 {v0, v5, v2, v3, v1, v4}

上图即为所求的最小生成树