专栏首页JavaEE普里姆算法(修路问题)

普里姆算法(修路问题)

一、是什么?

1. 应用场景:

有7个村庄(A, B, C, D, E, F, G) ,现在需要修路把7个村庄连通,各个村庄之间的距离如下。问如何修路,能使各个村庄连通且修路的总里程数最小?

修路问题

这就是经典的修路问题,就可以用普里姆算法来解决。

2.最小生成树:

要使总里程数最小,那么就要尽可能修少路,并且修的每条路距离应该小,这样加起来的总里程数才会少。这就是求最小生成树(MST)的过程。关于最小生成树,介绍如下:

  • 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树 ;
  • N个顶点,一定有N-1条边;
  • 包含全部顶点;
  • N-1条边都在图中;

什么意思呢?下面是一个图和它对应的生成树:

生成树

这是这个图对应的其中三种生成树,每条边有权值,权值加起来最小的那棵树,就叫做最小生成树。求最小生成树,可以用普里姆算法克鲁斯卡尔算法

二、普里姆算法步骤:

修路问题

还是以这个图为例,普里姆算法过程如下:

  • 创建一个集合,保存选择的顶点。首先选取顶点A,表示从A开始处理,将A加入到集合中。与A直接连通的有C、B、G,其中AG的权值最小,所以选择的是G,G加入到集合中。
  • 现在集合中有A和G,和A直接诶连通且还没有访问过的顶点有C、B,和G直接连通且还没有访问过的顶点有E、B、F。其中权值最小的是GB,所以选择B,B加入到集合。
  • 现在集合中有A、G、B。和A直接连通且没访问过的有C,和G直接连通且没访问过的是E、F,和B直接连通且没访问过的是D。其中权值最小的GE,所以选择E,E加入到集合。

……

  • 按照上面的方法,直到所有村庄都加到了集合中。最后选择的是AGBEFDC。

三、代码实现:

要用代码实现上述过程,首先我们要用邻接矩阵将这个图构建出来。首先创建一个类,表示图:

/**
 * 图
 * @author zhu
 *
 */
class Graph{
    List<String> vertexs; // 存放顶点
    int[][] edges; // 邻接矩阵,存放边
    
    public Graph(List<String> vertexs, int[][] edges) {
        this.vertexs = vertexs;
        this.edges = edges;
    }
}

然后,创建一个最小生成树类:

class MinTree{
    /**
     * 创建图
     * @param vertex 顶点集合
     * @param edges 邻接矩阵
     */
    public Graph createGraph(List<String> vertex, int[][] edges) {
        return new Graph(vertex, edges);
    }
    
    /**
     * 打印图的二维数组
     * @param graph
     */
    public void printGraph(Graph graph) {
        int[][] edges = graph.edges;
        for (int i=0; i<edges.length; i++) {
            System.out.println(Arrays.toString(edges[i]));
        }
    }
}

现在,就要在最小生成树类中用普里姆算法创建最小生成树,中MinTree类中加一个方法,如下:

/**
* 普里姆算法创建最小生成树
* @param graph 图
* @param currentVertex 开始处理的顶点
*/
public Map<String, Integer> prim(Graph graph, String currentVertex) {
    Map<String, Integer> resultMap = new HashMap<>(); // 保存结果的集合,key是两个顶点,value是这两个顶点边的长度
    List<String> vertexs = graph.vertexs; // 图的顶点
    int vertexCount = vertexs.size(); // 顶点的个数
    int currentVertexIndex = vertexs.indexOf(currentVertex); // 当前处理顶点的索引
    boolean[] isVisited = new boolean[vertexCount]; // 顶点是否被访问过
    isVisited[currentVertexIndex] = true; // 标记当前处理的顶点为已访问
    int num = 10000; // 初始化一个较大的数,用来比较权值的
    int index1 = -1; // 记录找到的两个顶点的索引
    int index2 = -1; // 记录找到的两个顶点的索引
    // n个顶点要生成n-1条边,所以循环n-1次
    for (int times=0; times<vertexCount-1; times++) {
        for (int i=0; i<vertexCount; i++) { // i表示访问过的顶点
            for (int j=0; j<vertexCount; j++) { // j表示未访问过的顶点
                if (isVisited[i] && !isVisited[j] && graph.edges[i][j] < num) {
                    num = graph.edges[i][j];
                    index1 = i;
                    index2 = j;
                }
            }
        }
        resultMap.put("<" + vertexs.get(index1) + "," + vertexs.get(index2) + ">", num);
        isVisited[index2] = true;
        // 重置num
        num = 10000;
    }
    return resultMap;
}

关于这个方法也很好理解,也有详细的注释。下面就可以写个测试方法,将案例中的图构建出来,求出修路的方案:

public static void main(String[] args) {
        List<String> vertexs = new ArrayList<>();
        vertexs.add("A");
        vertexs.add("B");
        vertexs.add("C");
        vertexs.add("D");
        vertexs.add("E");
        vertexs.add("F");
        vertexs.add("G");
        
        int[][] edges = new int[][] {
            // 100表示没有连通
            //A    B    C   D     E    F   G
            {100,   5,   7, 100, 100, 100, 2},  // A
            {  5, 100, 100,   9, 100, 100, 3},  // B
            {  7, 100, 100, 100,   8, 100, 100},// C
            {100,   9, 100, 100, 100,   4, 100},// D
            {100, 100,   8, 100, 100,   5, 4},  // E
            {100, 100, 100,   4,   5, 100, 6},  // F
            {  2,   3, 100, 100,   4,   6, 100} // G
        };
        
        MinTree minTree = new MinTree();
        Graph graph = minTree.createGraph(vertexs, edges);
        
        Map<String, Integer> resultMap = minTree.prim(graph, "A");
        for (String key : resultMap.keySet()) {
            System.out.println(key + ": " + resultMap.get(key));
        }
}

最后的结果是:

修路方案

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 普里姆(Prim)算法

    普里姆(Prim)算法,和克鲁斯卡尔算法一样,是用来求加权连通图的最小生成树的算法。 基本思想 对于图G4而言,V是所有顶点的集合;现在,设置两个新的集...

    机器学习算法工程师
  • 最小生成树算法(上)——Prim(普里姆)算法

    最小生成树:一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。根据定义可知对于一个有V个顶点的...

    AI那点小事
  • 算法:图解最小生成树之普里姆(Prim)算法

    我们在图的定义中说过,带有权值的图就是网结构。一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。所谓的最小成本,就...

    s1mba
  • 数据结构与算法-最小生成树之普里姆(Prim)算法

    Prim 算法可以称为“加点法”,每次迭代选择代价最小的边对应的点,加入到最小生成树中,算法从某一个顶点开始,逐渐长大覆盖整个连通网的所有顶点。

    越陌度阡
  • 克鲁斯卡尔算法(公交站问题)

    克鲁斯卡尔算法其实也是生成最小生成树的一种算法,和普里姆算法一样,解决同一类问题的。

    贪挽懒月
  • 2-2 畅通工程之局部最小花费问题 (30 分)【普利姆算法】

    某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城镇间都可以实现快速交通(但不一定有直接的快速道路...

    韩旭051
  • 数据结构01-最小生成树-Prim算法

    给定一个带权的无向连通图,能够连通该图的全部顶点且不产生回路的子图即为该图的生成树;

    yangjiao
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

    7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

    Kindear
  • 最短路径问题:Dijkstra算法

    所谓最短路径问题是指:如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边的权值总和(称为路径长度)达到最小。

    233333

扫码关注云+社区

领取腾讯云代金券