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

问题描述

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 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

C/C++ sizeof(下)

sizeof作用于基本数据类型,在特定的平台和特定的编译器中,结果是确定的,如果使用sizeof计算构造类型:结构体、联合体和类的大小时,情况稍微复杂一些。

722
来自专栏PHP技术

五个值得深思的PHP面试题

面试题 Q6 $x应该是输出什么? $x = true and false; var_dump($x); 部分同学或许会第一时间想到false,实际上这里依...

2745
来自专栏一个会写诗的程序员的博客

第5章 函数与函数式编程第5章 函数与函数式编程

函数式编程语言最重要的基础是λ演算(lambda calculus),而且λ演算的函数可以传入函数参数,也可以返回一个函数。函数式编程 (简称FP) 是一种编程...

491
来自专栏老九学堂

【必读】超全的C语言基础知识大全

我们用一个简单的c程序例子,介绍c语言的基本构成、格式、以及良好的书写风格,加深小伙伴们对C语言的认识。

992
来自专栏Micro_awake web

JavaScript(四):运算符&数据类型转换

+:算符的加法;连接字符串 加法会将其它类型的值,自动转为字符串,然后再进行连接运算! 1 var a=1+2; 2 console.log('first:...

1826
来自专栏海天一树

图的深度优先搜索

图有两种最基本的搜索算法,一种是深度优先搜索,另一种是广度优先搜索。本节先介绍深度优先搜索。

532
来自专栏IMWeb前端团队

JavaScript强化教程——JavaScript 运算符

本文作者:IMWeb 王军 原文出处:IMWeb社区 未经同意,禁止转载 本文为 H5EDU 机构官方 HTML5培训 教程,主要介绍:JavaScr...

1706
来自专栏用户2442861的专栏

剑指offer 33 把数组排成最小的数

转载请注明出处:http://blog.csdn.net/ns_code/article/details/28128551

702
来自专栏恰同学骚年

剑指Offer面试题:14.链表的倒数第k个节点

PS:这是一道出境率极高的题目,记得去年参加校园招聘时我看到了3次,但是每次写的都不完善。

684
来自专栏大数据钻研

一起来啃《JavaScript语言精粹》----对象

一、引言 任何编程语言在设计的时候就存在精华与糟粕并存,《JavaScript语言精粹》这本书就是取其精华,去其糟粕,能让我写出更优雅性能更好的JavaScri...

2676

扫描关注云+社区