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

问题描述

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

相关文章

来自专栏数据结构与算法

P2485 [SDOI2011]计算器

题目描述 你被要求设计一个计算器完成以下三项任务: 1、给定y、z、p,计算y^z mod p 的值; 2、给定y、z、p,计算满足xy ≡z(mod p)的最...

39210
来自专栏Petrichor的专栏

leetcode: 85. Maximal Rectangle

From LeetCode 笔记系列 18 Maximal Rectangle [学以致用]:

1213
来自专栏数据结构与算法

06:笨小猴

06:笨小猴 总时间限制:1000ms内存限制:65536kB描述 笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用...

2987
来自专栏数据结构与算法

P1378 油滴扩展

题目描述 在一个长方形框子里,最多有N(0≤N≤6)个相异的点,在其中任何一个点上放一个很小的油滴,那么这个油滴会一直扩展,直到接触到其他油滴或者框子的边界。必...

2638
来自专栏计算机视觉与深度学习基础

Leetcode 172 Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!. Note: Your sol...

1916
来自专栏数据结构与算法

P3379 【模板】最近公共祖先(LCA)

题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入输出格式 输入格式: 第一行包含三个正整数N、M、S,分别表示树的结点个数...

3526
来自专栏Deep Learning 笔记

MNIST__数字识别__SOFTMAX

本次MNIST的手写数字识别未采用input_data.py文件,想尝试一下用原始的数据集来运行这个DEMO。

1021
来自专栏C/C++基础

图的周游

图的周游:是一种按某种方式系统地访问图中的所有节点的过程,它使每个节点都被访问且只访问一次。图的周游也称图的遍历。

782
来自专栏算法与数据结构

PTA 数据结构 一元多项式求导 (仅供参考)

请勿粘贴 输入格式: 以指数递降方式输入多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。 输出格式: 以与输入相同的格式输出导数多项...

17510
来自专栏云霄雨霁

子字符串查找----各种算法总结

1730

扫码关注云+社区