贪心算法(四)——最小代价生成树

问题描述

n个村庄间架设通信线路,每个村庄间的距离不同,如何架设最节省开销?

这个问题中,村庄可以抽象成节点,村庄之间的距离抽象成带权值的边,要求最节约的架设方案其实就是求如何使用最少的边、最小的权值和将图中所有的节点连接起来。 这就是一个最小代价生成树的问题,可以用Prim算法或kruskal算法解决。

  • PS1:无向连通图的生成树是一个极小连通子图。
  • PS2:生成树是图的一个子图,包括所有的顶点和最少的边(n-1条边)。
  • PS3:最小代价生成树就是所有生成树中权值之和最小的那个。

算法思路

算法的目标很明确,就是要在n个节点的图中,找出n-1个节点,并且节点之间连线的权值是最小的。因此总体思路如下:

/**
 * @param a:图的邻接矩阵
 */
EdgeSet spanningTree(int[][] a){
    // 结果集(边的集合)
    EdgeSet solution = new EdgeSet();
    // 选出n-1条边
    int i = 0;
    while( i<n && 还有未检查的边 ){
        // 选出一条边
        Edge edge = Select(a);
        // 判断是否有回路
        if ( !hasLoop(edge) ) {
            solution.add( edge );
        }
    }
    return solution;
}

上述为最小代价生成树的总体思路,其中选边方式(贪心准则)的不同,就产生不同的最小代价生成树算法。

图的邻接表示法

边节点

一个边节点有一条边 和 一个终止节点组成。

/**
 * 边节点(由一条边和一个终止节点构成)
 */
class ENode{
    int id;// 终止节点的编号
    int weight;// 边的权重
}

图的邻接表示

图用一个Map< String,List>表示,其中String表示节点的编号,List中存储以该节点为起点的所有边节点。

Map<String,List<ENode>>

Prim算法

贪心准则:将整个图分成两部分,一部分已选入生成树,另一部分在生成树之外。每次选的边要求一头在生成树之内,一头在生成树之外,并保证当前边是满足上述条件中最短的一条。重复上述操作,直到选出n-1条边为止。

数据结构

  • mark: Map<String,Boolean> mark = new HashMap<>(); 记录指定节点是否已在生成树中。 key表示节点编号,value为boolean型,表示是否已选入生成树中。
  • nearest: Map<String,String> nearest; 用于记录最小代价生成树的那条路径。 key表示指定节点的编号; value表示在最小代价生成树中,该节点的前驱节点的编号。
  • lowcost: Map<String,Integer> lowcost; 记录指定节点为终点的边的最小权值。 key表示指定节点的编号; value表示在最小代价生成树中,以该节点为终点的边的权值。
  • k节点: 最新选入生成树的节点。

算法过程

第一步: 首先初始化数组: 1. mark的值全为false 2. nearest的值全为-1 3. lowcost的值全为Integer.MAX_VALUE。

mark[1]

mark[2]

mark[3]

mark[4]

mark[5]

mark[6]

false

false

false

false

false

false

lowcost[1]

lowcost[2]

lowcost[3]

lowcost[4]

lowcost[5]

lowcost[6]

MAX

MAX

MAX

MAX

MAX

MAX

nearest[1]

nearest[2]

nearest[3]

nearest[4]

nearest[5]

nearest[6]

-1

-1

-1

-1

-1

-1

第二步:

  1. 将节点1作为起点选入生成树,记为k,mark[1]=true;
  2. 遍历节点k的所有相邻节点,更新lowcost数组和nearest数组: 设j是节点k相邻节点,并且如果< k,j>这条边的权值小于lowcost[j],则更新lowcost[j]=w< k,j>、nearest[j]=k。
  3. 在lowcost数组中找到那个权值最小,且不在生成树中的边的节点,将它加入生成树中: 3.1. 遍历lowcost,找出最小值; 3.2. 将该最小值对应的lowcost下标(节点编号)的mark设为true; 3.3. 更新k;

mark[1]

mark[2]

mark[3]

mark[4]

mark[5]

mark[6]

true

false

false

false

false

false

lowcost[1]

lowcost[2]

lowcost[3]

lowcost[4]

lowcost[5]

lowcost[6]

MAX

6

1

5

MAX

MAX

nearest[1]

nearest[2]

nearest[3]

nearest[4]

nearest[5]

nearest[6]

-1

1

1

1

0

0

第三步:

  1. 此时将节点3记为k;
  2. 依次遍历与k节点相邻的所有不在生成树中的节点,并更新nearest数组和lowcost数组;
  3. 遍历lowcost数组,找出尚未选中的最短的边,将该边的终点设为true,并设为k,一直循环下去,直到选出n-1条边为止。

代码实现

/**
 * prim算法
 * @param graph:图的邻接矩阵
 */
void prim(Map<String,List<Edge>> graph){
    // 初始化
    Map<String,String> nearest = new HashMap<>();
    Map<String,Integer> lowcost = new HashMap<>();
    Map<String,Boolean> mark = new HashMap<>();
    String k = null;
    String end = null;// 记录最后一个节点的id,用于从后向前输出结果

    for( String id : graph.keySet() ){
        nearest.put( id, null );
        lowcost.put( id, Integer.MAX_VALUE );
        mark.put( id, false );
        k = id;
    }
    mark.put( id, true );

    // 寻找生成树的n-1条边
    for(int i=1; i<=graph.size()-1; i++){

        // 更新与k相邻的nearest
        List<ENode> edges = graph.get( k );
        for( ENode edge : edges ){
            if ( !mark.get(edge.id) && edge.w < lowcost.get(edge.id) ) {
                lowcost.put( edge.id, edge.w );
                nearest.put( edge.id, k );
            }
        }

        // 寻找当前lowcost中最短的边
        int min = Integer.MAX_VALUE;
        for( Map.Entry<String,Integer> entry : lowcost.entrySet() ){
            if ( entry.getValue() < min ) {
                min = entry.getValue();
                k = entry.getKey();
            }
        }
        mark.get( k, true );
        end = k;
    }

    // 输出结果
    for ( int i=0; i<graph.size(); i++ ) {
        System.out.println( nearest.get(end)+"-"+end+"权值:"+lowcost.get(end) );
        end = nearest.get(end);
    }
}

时间复杂度

若图中共有n个节点,那么Prim算法的时间复杂度为O(n^2)。

Kruskal算法

贪心准则:将所有的边按照权值递增的顺序排序,每次选一条权值最小的边纳入生成树中,若没有环路则选边成功,若有环路,则选下一条次小的边,直到选满n-1条边为止。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开源优测

[快学Python3]Number(数字)

概述 Python数值数据类型用于存储数值,并有一系列对应的函数用于处理数值类型的数据。 在Python中支持三种不同类型的数值类型: 整型(int) 通常称为...

2519
来自专栏King_3的技术专栏

leetcode-33-搜索旋转排序数组

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

853
来自专栏King_3的技术专栏

leetcode-867-Transpose Matrix(矩阵由按行存储变成按列存储)

Given a matrix A, return the transpose of A.

1222
来自专栏bboysoul

1493: C语言实验题――圆柱体计算

描述:已知圆柱体的底面半径r和高h,计算圆柱体底面周长和面积、圆柱体侧面积以及圆柱体体积。 输入:输入数据有一行,包括2个正实数r和h,以空格分隔。 输出:...

561
来自专栏Python攻城狮

科学计算工具Numpy1.ndarray的创建与数据类型2.ndarray的矩阵运算ndarray的索引与切片3.ndarray的元素处理元素判断函数元素去重排序函数4.2016年美国总统大选民意调查

Numpy:提供了一个在Python中做科学计算的基础库,重在数值计算,主要用于多维数组(矩阵)处理的库。用来存储和处理大型矩阵,比Python自身的嵌套列表结...

1173
来自专栏ACM算法日常

递归算法复杂度Ω分析-分享

1. 深入认识递归 (1) 递归执行过程 例子:求N!。 这是一个简单的"累乘"问题,用递归算法也能解决。 n! ...

421
来自专栏软件开发 -- 分享 互助 成长

二维数组简介与使用

前言 本文将探讨一下关于二维数组在内存中的存储和二维数组在参数传递时的使用。 一、二维数组在内存中的存储 如果定义一个这样的二维数组int a[3][4]={{...

19310
来自专栏Leetcode名企之路

【Leetcode】59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

1043
来自专栏余林丰

2.比较排序之梳排序

  梳排序的知名度远没有其他排序算法那么高,它是在冒泡排序的基础上做的改进,引入类似“步长”以及“子序列”概念,这两个概念在后面的排序算法中会经常提及。   待...

1838
来自专栏calmound

KMP专题

POJ 2406 Power Strings http://poj.org/problem?id=2406 题意:找出s字符窜由多少个重复子窜循环构成 分析:K...

2988

扫码关注云+社区