java数据结构和算法——普里姆(prim)算法

一、普里姆(prim)算法的介绍

• 普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图
• 普利姆的算法如下: 1)、设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合 2）、若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited[u]=1 3）、若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited[vj]=1 4）、重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边

二、最小生成树的介绍

• 最小生成树(Minimum Cost Spanning Tree)，简称MST
• 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
• N个顶点，一定有N-1条边
• 包含全部顶点
• N-1条边都在图中
• 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法
• 举例说明(如下图:)

三、普里姆算法——应用场景（修路问题）

有胜利乡有7个村庄(A, B, C, D, E, F, G) ，现在需要修路把7个村庄连通；各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里，问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?（如下图：）

四、普里姆算法——解决修路问题的思路图解

• 修路问题本质就是最小生成树问题

五、普里姆算法——解决修路问题的代码实现

• 使用邻接矩阵表示村庄修路的图，（如下图） 1）、表格中A行A列=10000，表示A和A两点不连通 2）、表格中A行B列=5，表示A和B两点可以连通，权值是5 3）、表格中A行C列=7，表示A和C两点可以连通，权值是7 4）、表格中A行D列=10000，表示A和D两点不连通 5）、依此类推…

• 代码

package com.rf.springboot01.Algorithm.prim;

import java.util.Arrays;

/**
 * @description: 普里姆算法（Prim算法）示例
 * @author: xz
 * @create: 2020-11-13 20:47
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        //定义图的各个顶点的值
        char[] data=new char[]{'A','B','C','D','E','F','G'};
        //根据图的各个顶点的值，获取图对应的顶点个数
        int verxs=data.length;
        //使用二维数组表示邻接矩阵的关系 ，10000:表示两个点不连通
        int[][] weight=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000}
        };
        //创建Graph对象
        Graph graph = new Graph(verxs);
        //创建MinTree对象
        MinTree minTree=new MinTree();
        //创建图的邻接矩阵
        minTree.createGraph(graph,verxs,data,weight);
        //显示图的邻接矩阵
        System.out.println("图的邻接矩阵----------------------");
        minTree.showGraph(graph);
        //测试普里姆算法
        System.out.println("普里姆算法==============");
        minTree.prim(graph,0);
    }
}

/** 
* @Description: 创建最小生成树->村庄的图
* @Author: xz  
* @Date: 2020/11/13 21:53
*/
class MinTree{
    /**
    * @Description:  创建图的邻接矩阵
    * @Param:  graph 图对象
    *          verxs 图对应的顶点个数
    *          data  图的各个顶点的值
    *          weight 图的邻接矩阵
    * @Author: xz
    * @Date: 2020/11/13 21:56
    */
    public void createGraph(Graph graph, int verxs, char[] data, int[][] weight){
        for(int i=0;i1...
    * @Author: xz
    * @Date: 2020/11/13 22:08
    */
    public void prim(Graph graph, int v) {
        //visited[] 标记结点(顶点)是否被访问过,visited[] 默认元素的值都是0, 表示没有访问过
        int visited[] = new int[graph.verxs];
        //把当前这个结点标记为已访问
        visited[v] = 1;
        //h1 和 h2 记录两个顶点的下标
        int h1 = -1;
        int h2 = -1;
        int minWeight = 10000; //将 minWeight 初始成一个大数，后面在遍历过程中，会被替换
        int sumMinWeight=0;//所有对应边的最小权值的总和
        for(int k = 1; k