普利姆算法

一、问题引出

在这里插入图片描述

二、最小生成树

在这里插入图片描述

三、普利姆算法介绍

在这里插入图片描述

四、图解分析

在这里插入图片描述

五、代码实现

package com.achang.algorithm;

import java.util.Arrays;

/**
 * 普利姆算法
 */
public class PrimAlgorithm {
    public static void main(String[] args) {

        //初始化最小生成树
        char[] data = {'a','b','c','d','e','f','g'};
        //临界矩阵的关系，用10000表示不连通
        int[][] weight = new int[][]{
                //a,b,c,d,e,f,g
                {10000,5,7,10000,10000,10000,2},//a
                {5,10000,10000,9,10000,10000,3},//b
                {7,10000,10000,10000,8,10000,10000},//c
                {10000,9,10000,10000,10000,4,10000},//d
                {10000,10000,8,10000,10000,5,4},//e
                {10000,10000,10000,4,5,10000,6},//f
                {2,3,10000,10000,4,6,10000},//g
        };

        Graph graph = new Graph(data.length);
        MinTree minTree = new MinTree();
        minTree.createGraph(graph,
                data.length,
                data,
                weight);
        minTree.list(graph);
        //使用普利姆算法生成最小生成树
        minTree.prim(graph,0);



    }
}

//创建最小生成树，村庄图
class MinTree{
    /**
     * 创建图的临界矩阵
     * @param graph 图对象
     * @param verxs 图对应的节点个数
     * @param data 图各个节点的值
     * @param weight 图的临界矩阵
     */
    public void createGraph(Graph graph,int verxs,char[] data,int[][] weight){
        int i,j;
        for (i = 0; i < verxs; i++) {
            graph.data[i] = data[i];
            for (j = 0; j < verxs;j++){
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    //遍历图的临界矩阵
    public void list(Graph graph){
        for (int[] ints : graph.weight) {
            System.out.println(Arrays.toString(ints));
        }
    }

    /**
     * 普利姆算法，得到最小生成树
     * @param graph 图结构
     * @param v 表示从图结构的第几个节点开始生成 'a'->0
     *                                    'b'->1
     *                                    'c'->2
     *                                     .....
     */
    public void prim(Graph graph,int v){
        //表示标记节点是否被访问过，元素值为0，表示没有被访问过
        int[] visited = new int[graph.verxs];

        visited[v] = 1;
        //用h1、h2记录两个节点的下标
        int h1 = -1;
        int h2 = -1;
        //初始化minWeight为一个大数，后面会被替换更改
        int minWeight = 10000;

        //因为有graph.verxs个节点，那普利姆算法结束后，有graph.verxs-1条边
        //确定每一次生成的子图，和哪个节点和这次遍历节点的记录【权值】最近
        for (int i = 1; i < graph.verxs; i++) {//i节点表示，被访问过的节点
            for (int j = 0; j < graph.verxs; j++) {//j节点表示，还没有访问过的节点
                for (int k = 0; k < graph.verxs; k++) {
                    if (visited[j]==1 && visited[k] == 0 && graph.weight[j][k] < minWeight){
                        //替换minWeight，寻找已经访问过的节点和未访问过的节点间，权值最小的边
                        minWeight = graph.weight[j][k];
                        //并记录此节点的下标
                        h1 = j;
                        h2 = k;
                    }
                }
            }
            //退出了上面的for循环后就找到了这条边
            System.out.println("边<"+graph.data[h1]+","+graph.data[h2]+">权值："+minWeight);
            //将当前节点，标记为已访问节点
            visited[h2] = 1;
            //重置minWeight
            minWeight = 10000;
        }
    }

}

//图结构
class Graph{
    int verxs;//图节点个数
    char[] data;//保存节点的数据
    int[][] weight;//存放边值，临界矩阵

    public Graph(int size){
        this.verxs = size;
        data = new char[verxs];
        weight = new int[verxs][verxs];
    }
}