基于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<>(Comparator.comparingInt(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);
    }

    @Override
    public void buildMST() {
        // 选择一个初始顶点，将该顶点关联的所有边加入队列
        for (int i = 0; i < size; i++) {
            if (matrix[0][i] == 0) continue; // matrix[0][i] == 0 表示不连通
            visited.add(vertex.get(0)); // 记录被访问过的顶点
            queue.add(new Edge<>(matrix[0][i], vertex.get(0), vertex.get(i))); // 将边加入优先队列
        }
		// 从队列取边
        while (!queue.isEmpty()) {
            Edge<E> edge = queue.poll();
            E from = edge.getFrom();
            E to = edge.getTo();
            // 如果边关联的顶点都已经被访问，跳过
            if (visited.contains(from) && visited.contains(to)) {
                continue;
            }
			// 打印构成最小生成树的边，from {U} to {V}, edge weight: {weight}
            System.out.println("from " + from + " to " + to + ", " + "edge weight: " + edge.getWeight());

            // 前面是将跟某个顶点关联的边加入优先队列，所以从队列中取出的边有且仅有一个顶点未被访问过
            E e = visited.contains(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 && !visited.contains(vertex.get(i))) {
                    queue.add(new Edge<>(matrix[index][i], e, vertex.get(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 = mergeFindSet.get(key);
        if (!value.equals(key)) {
            value = search(value);
            mergeFindSet.put(key, value);
        }
        return value;
    }

    public void setMergeFindSet(Map<E, E> mergeFindSet) {
        this.mergeFindSet = 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));
    }

    @Override
    public 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], vertex.get(i), vertex.get(j))); // 把边加入优先队列
                }
            }
        }
        while (!queue.isEmpty()) { // 从队列里面取权重最小的边
            Edge<E> edge = queue.poll();
            E from = edge.getFrom();
            E to = edge.getTo();
            // 边联通的两个节点尚未在同一个集合，合并
            if (mergeFindSet.search(from) != mergeFindSet.search(to)) {
                mergeFindSet.union(from, to);
                System.out.println("from " + from + " to " + to + ", " + "edge weight: " + edge.getWeight());
            }
        }
    }
}

测试类

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算法代码实现，在实现的过程中不仅仅追求的是算法思想，也在思考怎么把代码写得更加优雅，所以也尝试使用了抽象类、泛型等，但是还是很多地方写得不太好，还有优化的空间，好好加油吧！

原文链接：https://blog.csdn.net/faker7/article/details/127841413

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

定义

算法

Prim算法

思想

Kruskal算法

思想

代码实现

定义边的数据结构

定义最小生成树的抽象类

Prim算法实现

Kruskal算法实现

并查集实现

Kruskal算法实现

测试类

总结

你可能也喜欢