当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

POJ 1789 最小生成树之prim算法

发表于: 2012-10-24   作者:128kj   来源:转载   浏览:
摘要: 1、生成树    如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树(SpanningTree)。 生成树是连通图的包含图中的所有顶点的极小连通子图,图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。 2、 最小生成树   对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总和称为该树的权,权最小的
1、生成树
   如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树(SpanningTree)。
生成树是连通图的包含图中的所有顶点的极小连通子图,图的生成树不惟一。从不同的顶点出发进行遍历,可以得到不同的生成树。

2、 最小生成树
  对于连通的带权图(连通网)G,其生成树也是带权的。生成树T各边的权值总和称为该树的权,权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。

3、MST性质

   假设N=(V,{E})是一个连通网,U是顶点集合V的一个非空子集。若(u,v)是一条具有最小值(代价)的边,其中u属于U,v属于V-U(即U对立集合),那么必存在一颗包含边(u,v)的最小生成树。

注意prim和kruskal算法都是利用MST性质

Prim算法求最小生成树的基本思想:

  1.首先选取一个点作为起始点,比如说1顶点,加入到U集合中

    2.在所有u∈U,v∈V-U的边(u,v)∈E中,找一条权最小的边(u,v),将此边加进集合T中,并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V-U中,其次边的权要最小。找到这条边以后,把这条边放到边集T中,并把这条边上不在U中的那个顶点加入到U中。

     3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n-1次(设n为图中顶点的数目),TE中也增加了n-1条边,这n-1条边就是需要求出的最小生成树的边。

例:POJ1789

题意:给出n台卡车的条形码(7位字符串),每两台卡车之间的距离为两条条形码相比较相同位置字符不同的个数,让求出包含所有卡车的最小距离。
Sample Input

4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0

Sample Output

The highest possible quality is 1/3.

解题: 如果按照上述关系建立图,节点为卡车的编号,边的权值为卡车之间的距离,很容易将本题目变为求一个图的最小生成树问题了。

import java.util.Scanner;
import java.util.Arrays;
public class Main{
  private int n; //卡车的数目
  private int G[][];//邻接矩阵
  String[] s;//n台卡车的条形码

  public Main(int n,String s[]){
      this.n=n;
      this.s=s;
      G=new int[n+1][n+1];
      init();
     
   }

  private int getdis(String s,String t)/* 得到两台卡车之间的而距离 */
  { 
    int tmp=0; 
    for(int i=0;i<7;i++) 
    { 
        if(s.charAt(i)!=t.charAt(i)) tmp++; 
    } 
    return tmp; 
  } 
  
  public static void main(String args[]){
      Scanner in=new Scanner(System.in);
     while(true){
      int n=in.nextInt();
      if(n==0) break;
      String s[]=new String[n+1];
      for(int i=1;i<=n;i++)
         s[i]=in.next();
      Main m=new Main(n,s);
      System.out.println("The highest possible quality is 1/"+m.prim()+"."); 
     }


   }

    
  private void init(){/* 输入数据 建立邻接矩阵 */ 
    for(int i=1;i<=n;i++){ 
        G[i][i]=Integer.MAX_VALUE; 
        for(int j=i+1;j<=n;j++) 
        { 
            int t=getdis(s[i],s[j]); 
            G[i][j]=G[j][i]=t; 
        } 
    } 
  } 

    public int prim(){
       int sum = 0;
       boolean flag[]=new boolean[n+1];
       flag[1] = true; //选取第一个卡车进入U集
                 
       for(int k=1; k< n; k++){    //循环n-1次,选取n-1条边
         int min = Integer.MAX_VALUE,min_i = 1;
         for(int i=1; i<=n; i++){
           if( !flag[i] && G[1][i] < min){
            min = G[1][i];
            min_i = i;
           }
          }
                
        flag[min_i] = true; //
        for(int i=1; i<= n; i++){ 
          if( !flag[i] && G[1][i] > G[min_i][i]){
              G[1][i] = G[min_i][i];
          }               
       }
              
       sum += G[1][min_i];//加上权值
     }          
            
    return sum;
            
  }
}

源码下载:

POJ 1789 最小生成树之prim算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到
Prim算法: 假设N = (V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0属于V),
转载地址:http://blog.chinaunix.net/uid-25324849-id-2182922.html 边赋以权值的图称为网或带权图
prim算法是生成最小生成树的一个重要方法,它非常类似于最短路径的Dijastra算法. Prim算法的特点是
  定义:设G=(V,E)是一个无向连通图。如果G的生成子图T=(V,E’)是一棵树,则称T是G的一棵生成树(Sp
在一个具有几个顶点的连通图G中,如果存在子图G'包含G中所有顶点和一部分边,且不形成回路,则称G'
Prim 算法是一种解决最小生成树问题(Minimum Spanning Tree)的算法。和 Kruskal 算法类似,Prim
Prim算法 1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意
MST-PRIM(G, w, r) // G: graph, w: weight, r:root 1 for each u ∈ V [G] 2 do key[u] ← ∞ 3 π
Prim算法 1 .概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号