（JAVA）加权无向图和最小生成树的实现与原理概述

package com.renecdemo.prim;

import com.renecdemo.graph.Queue;
import com.renecdemo.queue.IndexMinPriorityQueue;
import com.renecdemo.weighted.Edge;
import com.renecdemo.weighted.EdgeWeightedGraph;

// Prim算法实现最小生成树
public class PrimMST {
    // 索引代表顶点，值表示当前顶点和最小生成树之间的最短边
    private Edge[] edgeTo;
    // 索引代表顶点，值表示当前顶点和最小生成树之间的最短边的权重
    private double[] distTo;
    // 索引代表顶点，如果当前顶点已经在树中，则值为true，否则为false
    private boolean[] marked;
    // 存放树中和非树中顶点之间的有效横切边
    private IndexMinPriorityQueue<Double> pq;

    // 根据一副加权无向图，创建最小生成树计算对象
    public PrimMST(EdgeWeightedGraph G) {
        // 初始化变量
        this.edgeTo = new Edge[G.V()];
        this.distTo = new double[G.V()];

        // 初始化权重
        for (int i = 0; i < distTo.length; i++) {
            // 让double数组中的每个值都等于Double类型所能存储的最大值
            // 当权重默认为无限大时，意味着该边永远不可能是最短边
            distTo[i] = Double.POSITIVE_INFINITY;
        }


        this.marked = new boolean[G.V()];
        this.pq = new IndexMinPriorityQueue<Double>(G.V());//16

        // 默认让顶点0进入到树中，当树中只有一个顶点0
        distTo[0] = 0.0;// 顶点0 的权重为 0.0
        pq.insert(0,0.0);// 它的横切边为 0， 该边权重为0.0

        // 遍历所以最小优先队列
        while (!pq.isEmpty()){
            // 切分 - 对 顶点0 进行切分
            visit(G,pq.delMin());
        }

    }

    // 将顶点v添加到最小生成树中，并且更新数据
    private void visit(EdgeWeightedGraph G,int v){
        // 把顶点v添加到最小生成树中
        marked[v] = true;// 标识 顶点v 在树中已存在

        /*
            遍历 G图 中 顶点v 的邻接表
         */
        for (Edge e : G.adj(v)) {
            int w = e.other(v);// 获得v顶点外的另一个顶点

            /*
                判断 w 顶点是否在树中，如果在，那么进行下一次循环
                    - 如果 w顶点 在树中就无需为w顶点添加到树中了
             */
            if (marked[w]){
                continue;
            }

            /*
                判断边 e边 的权重是否小于从w到树中已经存在最小边的权重
                    - 小于才做更新操作
             */
            if (e.weight()<distTo[w]){
                // 更新数据；更新记录的权重和最短边
                edgeTo[w] = e;
                distTo[w] = e.weight();

                // 更改优先队列中顶点的权重
                if (pq.contains(w)){
                    pq.changeItem(w,e.weight());
                }else {
                    pq.insert(w,e.weight());
                }
            }
        }
    }

    // 获取最小生成树的所有边
    public Queue<Edge> edges(){
        // 创建队列edges
        Queue<Edge> allEdge = new Queue<>();
        for (int i = 0; i < edgeTo.length; i++) {
            if (edgeTo[i] != null){
                allEdge.enqueue(edgeTo[i]);
            }
        }

        return allEdge;
    }
}

package com.renecdemo.graph;

import com.renecdemo.queue.MinPriorityQueue;
import com.renecdemo.weighted.Edge;
import com.renecdemo.weighted.EdgeWeightedGraph;
import com.renexdemo.tree.UF_Tree_Weighted;

/**
 * Kruskal 算法实现
 */
public class KruskalMST {
    // 保存最小生成树的所有边
    private Queue<Edge> mst;
    /**
     * 索引代表顶点，
     * 使用connect方法可以判断两个顶点是否在同一颗树中，
     * 使用union方法可以将两个顶点所在的树合并
     */
    private UF_Tree_Weighted uf;
    // 存储图中所有的边，使用最小优先队列，对边按照权重进行排序
    private MinPriorityQueue<Edge> pq;

    /**
     * 初始化构造
     * @param G
     */
    public KruskalMST(EdgeWeightedGraph G){
        // 初始化
        this.mst = new Queue<>();
        this.uf = new UF_Tree_Weighted(G.V());
        this.pq = new MinPriorityQueue<>(G.E()+1);

        // 把图中所有的边添加到pq中
        for (Edge e : G.edges()) {
            pq.insert(e);
        }

        /*
            pq数组不为空
            并且
            最小生成树的所有边不应该小于子图中顶点数-1
                - 如果所有边小于 子图中顶点数-1 那么代表最小生成树已经规划完毕
         */
        while (!pq.isEmpty() && mst.size() < G.V()-1){
            // 找到权重最小的边
            Edge e = pq.delMin();

            // 找到该边的两个顶点
            int v = e.either();
            int w = e.other(v);

            // 判断这两个顶点是否已经在同一棵树中
            if (uf.connected(v,w)){
                // 在一棵数中不做处理直接跳过当前循环
                continue;
            }
            // 不再一棵树中，那么合并
            uf.union(v,w);

            // 让边e进入到mst队列汇总
            mst.enqueue(e);
        }

    }

    /**
     * 获取最小生成树的所有边
     * @return
     */
    public Queue<Edge> edges(){
        return mst;
    }
}