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

POJ 1679 练习克鲁斯卡尔kruskal 算法

发表于: 2012-10-29   作者:128kj   来源:转载   浏览:
摘要: 克鲁斯卡尔kruskal 算法     假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:    先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,
克鲁斯卡尔kruskal 算法 
   假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:
   先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至子图中含有 n-1条边为止。

POJ1679:The Unique MST

题意:给一个无向图,判断这个图的最小生成树MST是否是唯一的。如果是唯一的,输出最小生成树的权值,如果不是唯一的,输出“Not Unique!” 

分析:先求出一棵最小生成树,记下最小权值为mst.然后枚举树上的每条边,去掉以后再求一次最小生成树,只要出现权值等于mst,那么最小生成树一定不唯一.


样例:
Sample Input

2(测试次数)
3 3(顶点和边的数目)
1 2 1(一条边的两个顶点和权值,以下同)
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

Sample Output

3
Not Unique!


AC代码:
import java.util.Scanner;      
import java.util.Arrays;      
public class Main{      
    private int father[];    //记录顶点的父节点  
    private Edge e[];   //图的所有边   
    private int n;//结点个数      
    private int l;//边的数目 
    private int mst;//最小生成树的最小权值
    private boolean uni;//最小生成树是否唯一的标志

    public Main(int n,int l,Edge[] e){      
       this.n=n;      
       this.l=l;      
       this.e=e;      
       father=new int[n+1];  
       mst=0;
       uni=true;    
       make_set();     
          
             
    }         

   private void make_set(){//将每个顶点初始化为一个集合(树),父节点指向自己。 
     for( int x = 1; x <= n; x ++)
        father[x] = x;
   }


   private int find_set(int x){//找x的父节点
    if(x != father[x])
        father[x] = find_set(father[x]);//路径压缩
    return father[x];
    }

    public int getMst(){
      return this.mst;
    }

    public boolean getUni(){
      return this.uni;
    }

  private void kruskal(){
    int  x, y;
    int mst_e[]=new int[n];//用于记录第一次krushal得到的MST的边
    int edge_num=0;//第一次krushal后的边数;
    int k = 0;
      // 下面为第一次kruskal求MST。
    make_set();    
    Arrays.sort(e);//将边按权值排序(从小到大)
     for(int i = 0; i < l; i ++){
        x = find_set(e[i].a);
        y = find_set(e[i].b);
        if(x != y){
            father[y] = x;//合并两棵树
            mst += e[i].weight;
            mst_e[k ++] = i;   //  记录下MST的边。
        }
    }
    edge_num = k;//  记录MST的边的数目
   
   
    for(int r = 0; r < edge_num; r ++){//枚举树上的每条边,去掉以后再求一次最小生成树,
         make_set();     //  每次kruskal要记得初始化并查集。
         int sec_mst=0;//用于记录下面求出的最小生成树的最小权值
         int num = 0;
        for(int i = 0; i < l; i ++){
            if(i == mst_e[r]) continue;   //  模拟删边。
            x = find_set(e[i].a);
            y = find_set(e[i].b);
            if(x != y){
                father[y] = x;
                sec_mst += e[i].weight;
                num ++;
            }
        }
        if(num != edge_num) continue;   //判断是能构成完整的次小生成树。
        if(sec_mst == mst){
         //System.out.println(mst);
  //如果能构造成完整的次小生成树,并且次小生成树的值与mst相等,则说明MST不唯一。
            uni = false;
            return;
        }
    } 
}

 

 public static void main(String args[]){
    Scanner in=new Scanner(System.in);
    int t=in.nextInt();
    
    while(t -->0){
        int n=in.nextInt();//顶点数
        int m=in.nextInt();//边数
        Edge[] e=new Edge[m];   
      for(int i = 0; i <m; i++){   
          e[i]=new Edge(in.nextInt(),in.nextInt(),in.nextInt());   
             
      }   
      Main ma=new Main(n,m,e);   
     
      ma.kruskal();
        if(!ma.getUni()) System.out.printf("Not Unique!\n");
        else System.out.printf("%d\n", ma.getMst());
    }
  }
  
}


class Edge implements Comparable       
     
{        
     int a;  //边的一个顶点,从数字0开始      
     int b;  //边的另一个顶点      
     int weight;  //权重      
     
     Edge(int a,int b,int weight){      
      this.a=a;      
      this.b=b;      
      this.weight=weight;      
    }      
     
    @Override         
    public int compareTo(Object o){       
        Edge m = (Edge)o;       
        int result=(int)(this.weight - m.weight);       
        if(result>0) return 1;      
        else if(result==0) return 0;      
        else return -1;      
    }       
     
}    

POJ 1679 练习克鲁斯卡尔kruskal 算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
设有一个有n个顶点的连通网N={V,E},最初先构造一个只有n个顶点, 没有边的非 连通图 T={V, E}, 图中
我们在前面讲过的《克里姆算法》是以某个顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树
算法描述 克鲁斯卡尔算法是一种贪心算法,因为它每一步都挑选当前最轻的边而并不知道全局路径的情况
1、基本思想:设无向连通网为G=(V, E),令G的最小生成树为T=(U, TE),其初态为U=V,TE={ },然
克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分
//Kruskal(克鲁斯卡尔)算法 //杨鑫 #include <stdio.h> #include <stdlib.h> #define M
#include <iostream> #include <string> using namespace std; typedef struct MGraph{
克鲁斯卡尔算法: 假设连通网N = {V,{E}},则令最小生成树的初始状态为只有n个顶点而无边的非连通图T
转自:克鲁斯卡尔算法(最小生成树) #include <iostream> #include <string> using na
#include <iostream> #include <string> using namespace std; typedef struct Edge//
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号