`
128kj
  • 浏览: 604190 次
  • 来自: ...
社区版块
存档分类
最新评论

最小生成树:Kruskal(克鲁斯卡尔)算法实现(java)

    博客分类:
阅读更多
算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问,所以克鲁斯卡尔算法的时间复杂度只和边又关系。

算法过程:

1.将图各边按照权值进行排序

2.将图遍历一次,找出权值最小的边,(条件:此次找出的边不能和已加入最小生成树集合的边构成环),若符合条件,则加入最小生成树的集合中。不符合条件则继续遍历图,寻找下一个最小权值的边。

3.递归重复步骤1,直到找出n-1条边为止(设图有n个结点,则最小生成树的边数应为n-1条),算法结束。得到的就是此图的最小生成树。
import java.util.Scanner;
import java.util.Arrays;
public class KruskalTest{
    private int father[];
    private int son[];
    private Edge e[];
    private int n;//结点个数
    private int l;//边的数目
       
    public KruskalTest(int n,int l,Edge[] e){
       this.n=n;
       this.l=l;
       this.e=e;
       father=new int[n];
       son=new int[n];
        for(int i = 0; i < n; ++i){   
            father[i] = i;//将每个顶点初始化为一个集合,父节点指向自己。
            son[i]=1;//初始化每个父节点的儿子数为1
        }        
    }   

    public static void main(String args[]){   
     
        Scanner scan = new Scanner(System.in);   
                 
        System.out.println("请输入测试次数:");   
        int ncase = scan.nextInt();   //测试次数
         
        while((ncase--)!=0){   
          int n = scan.nextInt();  //图的顶点数 
          int l = scan.nextInt();   //图的边数
          Edge[] e=new Edge[l];
          for(int i = 0; i < l ; ++i){//输入边的数据
            
            int a=scan.nextInt();
            int b=scan.nextInt();
            double weight=scan.nextDouble();
            e[i]=new Edge(a,b,weight);
          }
          KruskalTest spt = new KruskalTest(n,l,e);   
         System.out.println(spt.kruskal());  
       } 
    }

  
    public int unionsearch(int x){ //查找根结点+路径压缩   
       return (x == father[x]) ? x : unionsearch(father[x]);  
    }  
  
    public boolean join(int x, int y){ //合并   
       int root1, root2;  
       root1 = unionsearch(x);  
       root2 = unionsearch(y);  
       if(root1 == root2){ //为环   
          return false;  
       }
       else if(son[root1] >= son[root2]){  
            father[root2] = root1;  
            son[root1] += son[root2];  
        }  
        else  
        {  
            father[root1] = root2;  
            son[root2] += son[root1];  
        }  
        return true;  
     }  


     public double kruskal(){
        double sum=0;
        int ltotal=0;
        boolean flag=false;
        
        Arrays.sort(e); //按权值由小到大排序   
        for(int i = 0; i < l; ++i)  
        {  
            if(join(e[i].a, e[i].b)==true)  
            {  
                ltotal++; //边数加1   
                sum += e[i].weight; //记录权值之和   
                System.out.println(e[i].a+"-->"+e[i].b);
            }  
            if(ltotal == n - 1) //最小生成树条件:边数=顶点数-1   
            {  
                flag = true;  
                break;  
            }  
        }  
        if(flag) return sum;  
        else{
            System.out.println("此图没有最小生成树");
            return -1;
        }
     }
  }  
   

class Edge implements Comparable 

{  
     int a;  //边的一个顶点,从数字0开始
     int b;  //边的另一个顶点
     double weight;  //权重

     Edge(int a,int b,double 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;
    } 

}


运行:
C:\test>java   KruskalTest
请输入测试次数:
2
5 8
0 1 2
1 4 9
1 2 8
4 3 7
3 0 10
0 2 12
2 3 6
2 4 3
0-->1
2-->4
2-->3
1-->2
19.0
7 9
0 1 28
1 2 16
2 3 12
0 5 10
4 3 22
4 6 24
4 5 25
1 6 14
3 6 18
0-->5
2-->3
1-->6
1-->2
4-->3
4-->5
99.0
下载源码:
分享到:
评论

相关推荐

    Kruskal克鲁斯卡尔算法构造最小生成树的动画.zip

    《克鲁斯卡尔算法:构建最小生成树的精要解析》 在图论的世界里,寻找最优化解决方案是一项常见的挑战。其中,构造最小生成树(Minimum Spanning Tree, MST)是一个核心问题,它旨在找到一个无环连通子图,使得连接...

    最小生成树 克鲁斯卡尔算法 kruskal

    在MATLAB环境中实现克鲁斯卡尔算法,你可以参考名为"kruskal.m"的文件。这个文件很可能是包含了克鲁斯卡尔算法的具体实现,通过读取图的邻接矩阵或者边列表,进行上述步骤的计算。而"huan.m"文件可能是一个辅助函数...

    图的最小生成树,克鲁斯卡尔算法,普利姆算法

    在这个场景下,我们将深入探讨两种经典算法:克鲁斯卡尔算法(Kruskal's Algorithm)和普利姆算法(Prim's Algorithm)。 首先,克鲁斯卡尔算法是一种贪心策略,其基本思想是从最小的边开始逐步连接顶点,但要确保...

    Prim与Kruskal算法的最小生成树matlab实现

    在通信网理论作业3-最小生成树这个项目中,你可能会学习如何用MATLAB编写代码,实现Prim和Kruskal算法,并对给定的网络图数据进行最小生成树的构造。这将涉及到数据结构的设计、图的遍历以及最小生成树的验证等编程...

    头歌数据结构图的最小生成树算法

    通过普里姆算法和克鲁斯卡尔算法,我们可以有效地构建最小生成树。普里姆算法适合于稠密图,而克鲁斯卡尔算法则更适合稀疏图。此外,选择邻接矩阵还是邻接表进行存储也会影响算法的效率。 通过上述分析,我们了解了...

    数据结构课程设计报告最小生成树Kruskal算法

    数据结构课程设计报告最小生成树Kruskal算法 数据结构课程设计报告中,我们将使用Kruskal算法来生成最小生成树,该算法是图论中的一种经典算法,能够在给定的图中找到最小生成树。下面,我们将对Kruskal算法的实现...

    最小生成树 克鲁斯卡尔算法

    克鲁斯卡尔(Kruskal)算法是一种求解最小生成树的经典算法,由约瑟夫·克鲁斯卡尔在1956年提出。以下是克鲁斯卡尔算法的详细解释: 1. **算法步骤**: - **初始化**:创建一个空的集合来存储最终的最小生成树的边...

    数据结构,最小生成树克鲁斯卡尔算法的实现.pdf

    在资源难点方面,实现克鲁斯卡尔算法的难点主要集中在图的存储结构设计、算法的具体实现、最小生成树的计算以及程序的优化和调试这四个方面。解决这些难点需要开发者有扎实的算法基础、熟悉数据结构的特性和使用,并...

    用Prim和Kruskal算法构造最小生成树

    ### 使用Prim和Kruskal算法构建最小生成树 在图论中,最小生成树(Minimum Spanning Tree, MST)是一个非常重要的概念。对于一个连通的无向图来说,如果存在一个子图,它包含原图的所有顶点,并且这些顶点通过边...

    3.0最小生成树之克鲁斯卡尔算法(添加生成树,添加画图).zip

    克鲁斯卡尔算法(Kruskal's Algorithm)是求解最小生成树的一种经典方法,由约瑟夫·克鲁斯卡尔在1956年提出。本项目以Java编程语言实现了这一算法,并结合图形界面,使得理解和应用更加直观。 首先,我们要理解...

    数据结构,最小生成树克鲁斯卡尔算法的实现.docx

    本文档描述的项目是使用C/C++编程语言实现克鲁斯卡尔算法,以构建最小生成树。最小生成树问题通常出现在网络连接优化场景中,例如在n个城市间建立通信网络,目标是以最低成本连接所有城市。克鲁斯卡尔算法就是解决这...

    最小生成树 prim 和克鲁斯卡尔

    为了解决这个问题,需要使用 Prim 和 Kruskal 两种方法来实现最小生成树的求解。 Prim 算法 Prim 算法是一种常用的最小生成树算法。该算法的思想是通过一系列不断扩张的子树来构造一棵最小生成树。它的实现过程...

    数据结构,最小生成树克鲁斯卡尔算法的实现 (2).docx

    克鲁斯卡尔算法(Kruskal's Algorithm)是一种用于寻找加权无向图的最小生成树的算法。最小生成树是指连接图中所有顶点的树,且边的权重之和最小。在构建通信网络或优化基础设施布局等实际问题中,克鲁斯卡尔算法...

    Python采用Kruskal(克鲁斯卡尔)算法实现最小生成树

    ### Python 实现 Kruskal(克鲁斯卡尔)算法构建最小生成树 #### 最小生成树的概念 最小生成树(Minimum Spanning Tree, MST)是针对一个无向加权连通图的一种特殊子图结构。它能够连接图中的所有顶点(节点),并且...

    克鲁斯卡尔构造最小生成树

    克鲁斯卡尔算法的基本思想是贪心策略,它按照边的权重从小到大进行选择,每次选取一条与当前生成树不形成环的边。具体步骤如下: 1. **初始化**:将图中的所有边按权重排序。 2. **创建空树**:初始时,最小生成树...

    C#实现最小生成树之克鲁斯卡尔算法(Kurskal)

    总结,克鲁斯卡尔算法是C#实现最小生成树的一种高效方法,结合并查集数据结构可以避免环路的形成。在实际编程中,要关注算法的时间复杂度和空间复杂度,以及如何优化代码以提高性能。同时,理解算法背后的逻辑和图论...

    数据结构,最小生成树克鲁斯卡尔算法的实现.doc

    - 通过克鲁斯卡尔算法的实现,理解了如何在实际编程中解决最小生成树问题。 - 学习了并查集等数据结构的应用,提高了算法设计能力。 9. **参考文献** - 可能参考的书籍和论文,如《算法导论》、《数据结构与算法...

    数据结构,最小生成树克鲁斯卡尔算法的实现 (2).pdf

    克鲁斯卡尔算法(Kruskal's Algorithm)是一种用于构造最小生成树的经典算法,它遵循“贪心”策略,即在每一步中都选择当前未加入树中的权值最小的边,只要这条边不形成环路。 在克鲁斯卡尔算法的实现中,通常需要...

Global site tag (gtag.js) - Google Analytics