基于Java的最小生成树代码实现

基于Java的最小生成树代码实现

基于Java的最小生成树代码实现

定义

• 最小生成树是一副连通加权无向图中一棵权值最小的生成树；
• 给定无向图G = (V, E)，(u, v)代表连接顶点u与顶点v的边，即(u, v) ∈ in ∈E，w(u, v)代表该边的权重，若存在T ⊆ subseteq ⊆E，且(V, T)为树，使得w(T)= ∑ ( u , v ) ∈ T w ( u , v ) sum_{(u, v)in{T}}w(u, v) ∑(u,v)∈T​w(u,v)的w(T)最小，则T为G的最小生成树；
• 当图存在权重相等的边，最小生成树可能存在多个，当图不存在权重相等的边，最小生成树唯一；

算法

Prim算法

思想

加点法，从任意顶点出发，将与该边连接的所有边加入边集，并标记为已访问，从边集选择最小权重的边，若（1）该边能够连接到新顶点，使用该边，并将新顶点所连接且之前未被访问过的边加入边集，（2）否则放弃该边；继续选边至构成一个包含n个顶点，n-1条边的树。

Kruskal算法

思想

加边法，先构造n个只含有孤立顶点的树，然后从边集选择最小权重的边，若（1）该边能够连接两个子树，则使用该边，并将两个子树构成新的树，（1）否则放弃该边；继续选边至构成一个包含n个顶点，n-1条边的树。

代码实现

定义边的数据结构

/*** 定义边的数据结构，顶点定义为泛型*/
class Edge<E> {private int weight; // 权重private E from;private E to;// getter and setter
}

定义最小生成树的抽象类

/*** 最小生成树算法抽象类*/
abstract class MSTAlgorithm<E> {/*** 节点数*/protected int size;/*** 节点数组，泛型，包含具体的节点信息*/protected List<E> vertex;/*** 邻接矩阵*/protected int[][] matrix;/*** 优先队列，用于存储和取用边*/protected Queue<Edge<E>> queue;/*** 抽象方法， 构建最小生成树*/public abstract void buildMST();/*** 初始化* @param vertex* @param matrix*/protected MSTAlgorithm(E[] vertex, int[][] matrix) {size = vertex.length;this.vertex = Arrays.asList(vertex);this.matrix = matrix;queue = new PriorityQueue<>(ComparatorparingInt(Edge::getWeight));}
}

Prim算法实现

public class Prim<E> extends MSTAlgorithm<E> {/*** 用于记录被访问过的顶点*/private Set<E> visited;public Prim(E[] vertex, int[][] matrix) {super(vertex, matrix);visited = new HashSet<>(size);}@Overridepublic void buildMST() {// 选择一个初始顶点，将该顶点关联的所有边加入队列for (int i = 0; i < size; i++) {if (matrix[0][i] == 0) continue; // matrix[0][i] == 0 表示不连通visited.(0)); // 记录被访问过的顶点queue.add(new Edge<>(matrix[0][i], (0), (i))); // 将边加入优先队列}// 从队列取边while (!queue.isEmpty()) {Edge<E> edge = queue.poll();E from = From();E to = To();// 如果边关联的顶点都已经被访问，跳过if (ains(from) && ains(to)) {continue;}// 打印构成最小生成树的边，from {U} to {V}, edge weight: {weight}System.out.println("from " + from + " to " + to + ", " + "edge weight: " + Weight());// 前面是将跟某个顶点关联的边加入优先队列，所以从队列中取出的边有且仅有一个顶点未被访问过E e = ains(from) ? to : from;visited.add(e);// 此处判断一下是否所有的顶点都已经连通了，即已经构成了最小生成树if (visited.size() == size) {break;}// 把该顶点连接的边加入队列int index = vertex.indexOf(e);for (int i = 0; i < size; i++) {if (matrix[index][i] != 0 && !(i))) {queue.add(new Edge<>(matrix[index][i], e, (i)));}}}}
}

Kruskal算法实现

因为Kruskal算法是先构造n个只含有孤立顶点的树，然后用边将子树连通；但是边连接的是两个顶点，需要判断两个顶点所在的树是否连通，用到一个数据结构叫并查集

并查集实现

并查集最主要的几个功能：合并（合并两个子树）、查询（查询两个子树所在的树是否连通）

/*** 并查集*/
class MergeFindSet<E> {public MergeFindSet() {}public MergeFindSet(Collection<E> collection) {init(collection);}/*** 集合元素个数*/private int size;/*** 并查集*/private Map<E, E> mergeFindSet;/*** 初始化集合，每个元素所属的集合代表元素就是自己*/public void init(Collection<E> collection) {size = collection.size();mergeFindSet = new HashMap<>(size);// 把元素拆分到不同的集合collection.forEach(e -> mergeFindSet.put(e, e));}/*** 查找元素所属的集合，当key != value，继续像前查找，key == value，自己就是集合代表元素* @param key 待查找元素* @return value 输入元素所在集合的代表元素*/public E search(E key) {E value = (key);if (!value.equals(key)) {value = search(value);mergeFindSet.put(key, value);}return value;}public void setMergeFindSet(Map<E, E> mergeFindSet) {FindSet = mergeFindSet;}/*** 按秩合并集合，把小集合合并到大集合* @param e1* @param e2*/public void union(E e1, E e2) {E root1 = search(e1);E root2 = search(e2);if (root1.equals(root2)) {return; // 元素在同一个集合，不需要合并}// 合并集合// TODO 把小集合合并到大集合// 因为目前是用HashMap来实现，没有记录集合的元素个数，所以无法按秩合并mergeFindSet.put(root1, root2);}}

此处也可以考虑把MergeFindSet定义成Kruskal的内部类

Kruskal算法实现

public class Kruskal<E> extends MSTAlgorithm<E> {/*** 并查集*/protected MergeFindSet<E> mergeFindSet;/*** 记录被访问过的边*/protected boolean[][] visited;public Kruskal(E[] vertex, int[][] matrix) {super(vertex, matrix);visited = new boolean[size][size];mergeFindSet = new MergeFindSet<>(Arrays.asList(vertex));}@Overridepublic void buildMST() {for (int i = 0; i < size; i++) {for (int j = 0; j < size; j++) {if (!visited[i][j] && matrix[i][j] != 0) {visited[i][j] = true;visited[j][i] = true;queue.add(new Edge(matrix[i][j], (i), (j))); // 把边加入优先队列}}}while (!queue.isEmpty()) { // 从队列里面取权重最小的边Edge<E> edge = queue.poll();E from = From();E to = To();// 边联通的两个节点尚未在同一个集合，合并if (mergeFindSet.search(from) != mergeFindSet.search(to)) {mergeFindSet.union(from, to);System.out.println("from " + from + " to " + to + ", " + "edge weight: " + Weight());}}}
}

测试类

class Test {public static void main(String[] args) {Character[] vertex = new Character[] {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; // 节点int[][] matrix = {{0, 8, 7, 0, 0, 0, 0}, {8, 0, 6, 0, 9, 8, 0}, {7, 6, 0, 3, 4, 0, 0}, {0, 0, 3, 0, 2, 0, 0},{0, 9, 4, 2, 0, 0, 10}, {0, 8, 0, 0, 0, 0, 2}, {0, 0, 0, 0, 10, 2, 0}}; // 邻接矩阵System.out.println("Prim buildMST:");Prim<Character> prim = new Prim<>(vertex, matrix);prim.buildMST();System.out.println("Kruskal buildMST:");Kruskal<Character> kruskal = new Kruskal<>(vertex, matrix);kruskal.buildMST();}
}

总结

以上，是对基于Java的最小生成树Prim和Kruskal算法代码实现，在实现的过程中不仅仅追求的是算法思想，也在思考怎么把代码写得更加优雅，所以也尝试使用了抽象类、泛型等，但是还是很多地方写得不太好，还有优化的空间，好好加油吧！