Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 1471|回复: 0

[算法学习]学习普里姆(Prim)算法求解图的最小生成树

[复制链接]
  • TA的每日心情
    开心
    2021-3-12 23:18
  • 签到天数: 2 天

    [LV.1]初来乍到

    发表于 2014-12-7 00:07:09 | 显示全部楼层 |阅读模式
    1、生成树
    如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树(SpanningTree)。
    生成树是连通图的包含图中的所有顶点的极小连通子图。
    图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。


    2、 最小生成树
       对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总和称为该树的权, 权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。 3、生成树和最小生成树的应用
    生成树和最小生成树有许多重要的应用。
    【例】网络G表示n各城市之间的通信线路网线路(其中顶点表示城市,边表示两个城市之间的通信线路,边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。 4、最小生成树性质(MST性质)
    MST性质
    最小生成树性质:设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。若(u,v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中具有最小权值的一条边,则一定存在G的一棵最小生成树包括此边(u,v)。

    注:将集合U中的顶点看作是红色顶点,②而V-U中的顶点看作是蓝色顶点,③连接红点和蓝点的边看作是紫色边,④权最小的紫边称为轻边(即权重最"轻"的边)。于是,MST性质中所述的边(u,v)就可简称为轻边。
      4、求MST的一般算法描述
    求MST的一般算法可描述为:针对图G,从空树T开始,往集合T中逐条选择并加入n-1条安全边(u,v),最终生成一棵含n-1条边的MST。
    当一条边(u,v)加入T时,必须保证T∪{(u,v)}仍是MST的子集,我们将这样的边称为T的安全边。

    用伪代码可将算法描述为:
    GenerieMST(G){//求G的某棵MST
       T={}; //T初始为空,是指顶点集和边集均空
       while T未形成G的生成树 do{
          找出T的一条安全边(u,v);//即T∪{(u,v)}仍为MST的子集
          T=T∪{(u,v)}; //加入安全边,扩充T
        }
       return T; //T为生成树且是G的一棵MST
    }

    5、普里姆(Prim)算法


    (1)算法思想
    T=(U,TE)是存放MST的集合。
    ①T的初值是({r},¢)
    即最小生成树初始时只有一个红点r,没有红边。
    ②T经过n-1次如下步骤操作,最后得到一棵含n个顶点,n-1条边的最小生成树
            ⒈选择紫边集中一条轻边并扩充进T
    ⒉将轻边连接的蓝点改红点
    ⒊将轻边改红边
            ⒋修改紫边集 (2)较小紫边集的构造
         若当前形成的T中有k个顶点,|U|=k,|V-u|=n-k,故可能的紫边数目是k(n-k)。从如此大的紫边集中选择轻边是低效的。因此,必须构造较小的紫边集。

        对于每个蓝点v ∈V-U,从v到各红点的紫边中,只有最短的那一条才有可能是轻边。因此,只须保留所有n-k个蓝点所关联的最短紫边作为轻边的候选集即可。 (3)候选紫边集合的修改
         当把轻边(u,v)扩充到T时,因为v由蓝变红,故对每个剩余的蓝点j,边(v,j)就由非紫边变为紫边,这条新紫边的长度可能小于蓝点j原来所关联的最短紫边的长度。因此,用长度更小的新紫边取代那些原有的最短紫边。 (4)Prim算法的伪代码描述
    PrimMST(G,T,r){
       //求图G的以r为根的MST,结果放在T=(U,TE)中
       InitCandidateSet(…);//初始化:设置初始的轻边候选集,并置T=({r},¢)
       for(k=0;k<n-1;k++){ //求T的n-1条树边
         (u,v)=SelectLiShtEdge(…);//选取轻边(u,v);
        T←T∪{(u,v)};//扩充T,即(u,v)涂红加入TE,蓝点v并人红点集U
        ModifyCandidateSet(…); //根据新红点v调整候选轻边集
       }
    } (5) 算法的执行过程
    用PRIM算法得到最小生成树的过程【参见动画演示】   
       

    注意:
    若候选轻边集中的轻边不止一条,可任选其中的一条扩充到T中。
    连通网的最小生成树不一定是惟一的,但它们的权相等。
      (6)算法特点
    该算法的特点是当前形成的集合T始终是一棵树。将T中U和TE分别看作红点和红边集,V-U看作蓝点集。算法的每一步均是在连接红、蓝点集的紫边中选择一条轻边扩充进T中。MST性质保证了此边是安全的。T从任意的根r开始,并逐渐生长直至U=V,即T包含了 C中所有的顶点为止。MST性质确保此时的T是G的一棵MST。因为每次添加的边是使树中的权尽可能小,因此这是一种"贪心"的策略。
    (7)算法分析
    该算法的时间复杂度为O(n2)。与图中边数无关,该算法适合于稠密图。 代码:
    1. import java.io.BufferedInputStream;
    2. import java.util.Scanner;
    3. import java.util.Arrays;
    4. public class PrimTest{
    5.     private int[][] arr;//邻接矩阵
    6.     private boolean flag[];  //用来标记节点是否已加入到MST,flag[i]=true表示i点变红,加入到MST
    7.     private int n; //顶点数
    8.     private int sum;//最小权值和
    9.     static final int maxInt = Integer.MAX_VALUE;
    10.     public PrimTest(int[][] arr,int n){
    11.          this.arr=arr;
    12.          this.n=n;
    13.          flag=new boolean[n];
    14.     }
    15.             
    16.      
    17.       public int prim(){
    18.             sum = 0;
    19.             flag[0] = true; //选取第一个节点为红点,将"0"加入红点集,开始时,所有点都是蓝点
    20.             int mst[]=new int[n];//用来存储最小权值边的起点
    21.             Arrays.fill(mst,0);//起点默认为0

    22.             
    23.             for(int k=1; k< n; k++){    //循环n-1次,选取n-1条边
    24.                 int min = maxInt,min_i = 0;
    25.                 for(int i=0; i< n; i++){//在所有紫边中选一条权值最小的。蓝点与红点连接的边为紫边
    26.                     if( !flag[i] && arr[0][i] < min){
    27.                         min = arr[0][i];
    28.                         min_i = i;
    29.                     }
    30.                 }
    31.                
    32.                 flag[min_i] = true; //找到红点min_i,标记它
    33.                 System.out.print("边"+mst[min_i]+"-"+min_i);
    34.                  System.out.println("--"+arr[0][min_i]);
    35.                  //arr[0][i]用来存放以i为终点的紫边的最小权值
    36.                 for(int i=0; i< n; i++){ //因为新增了一个红点,紫边集有了变化,
    37.                     if( !flag[i] && arr[0][i] > arr[min_i][i]){//若同一个蓝点点与两个红点相连接,取权值较小的。
    38.                         arr[0][i] = arr[min_i][i];
    39.                         mst[i] = min_i;//更新较小权值边的起点
    40.                    }
    41.                   
    42.                 }
    43.               
    44.                 sum += arr[0][min_i];//加上权值
    45.             }
    46.             
    47.             
    48.            return sum;
    49.             
    50.         }
    51.    
    52.     public static void main(String[] args) {
    53.         Scanner s = new Scanner(new BufferedInputStream(System.in));
    54.             
    55.             int n = 7;
    56.             int arr[][] ={{maxInt,28,    maxInt,maxInt,maxInt, 10,    maxInt},
    57.                  {28,    maxInt,16,    maxInt,maxInt, maxInt,14     },
    58.                  {maxInt,16,    maxInt,12,    maxInt, maxInt,maxInt},
    59.                  {maxInt,maxInt,12,    maxInt,22,     maxInt,18    },
    60.                  {maxInt,maxInt,maxInt,22,    maxInt, 25,    24    },
    61.                  {10,    maxInt,maxInt,maxInt,25,     maxInt,maxInt},
    62.                  {maxInt,14,    maxInt,18,    24,     maxInt,maxInt}};
    63.           System.out.println(new PrimTest(arr,n).prim());
    64.             
    65.      }
    66. }
    复制代码
    运行结果:
    C:        est>java PrimTest
    边0-5--10
    边5-4--25
    边4-3--22
    边3-2--12
    边2-1--16
    边1-6--14
    99

       
         
         
          
          

            
          

            
          
         
       

      


    源码下载:http://file.javaxxz.com/2014/12/7/000709078.zip
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2024-3-28 18:00 , Processed in 0.349974 second(s), 46 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表