Java实现Kruskal算法的示例代码

目录
  • 介绍
  • 一、构建后的图
  • 二、代码
  • 三、测试

介绍

构造最小生成树还有一种算法,即 Kruskal 算法:设图 G=(V,E)是无向连通带权图,V={1,2,...n};设最小生成树 T=(V,TE),该树的初始状态只有 n 个节点而无边的非连通图T=(V,{}),Kruskal 算法将这n 个节点看成 n 个孤立的连通分支。它首先将所有边都按权值从小到大排序,然后值要在 T 中选的边数不到 n-1,就做这样贪心选择:在边集 E 中选择权值最小的边(i,j),如果将边(i,j)加入集合 TE 中不产生回路,则将边(i,j)加入边集 TE 中,即用边(i,j)将这两个分支合并成一个连通分支;否则继续选择下一条最短边。把边(i,j)从集合 E 中删去,继续上面的贪心选择,直到 T 中的所有节点都在同一个连通分支上为止。此时,选取的 n-1 条边恰好构成图 G 的一棵最小生成树 T。

Kruskal 算法用一种非常聪明的方法,就是运用集合避圈;如果所选择加入边的起点和终点都在 T 集合中,就可以断定会形成回路,变的两个节点不能属于同一个集合。

算法步骤

1 初始化。将所有边都按权值从小到大排序,将每个节点集合号都初始化为自身编号。

2 按排序后的顺序选择权值最小的边(u,v)。

3 如果节点 u 和 v 属于两个不同的连通分支,则将边(u,v)加入边集 TE 中,并将两个连通分支合并。

4 如果选取的边数小于 n-1,则转向步骤2,否则算法结束。

一、构建后的图

二、代码

package graph.kruskal;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Kruskal {
    static final int N = 100;
    static int fa[] = new int[N];
    static int n;
    static int m;

    static Edge e[] = new Edge[N * N];
    static List<Edge> edgeList = new ArrayList();

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    // 初始化集合号为自身
    static void Init(int n) {
        for (int i = 1; i <= n; i++)
            fa[i] = i;
    }

    // 合并
    static int Merge(int a, int b) {
        int p = fa[a];
        int q = fa[b];
        if (p == q) return 0;
        for (int i = 1; i <= n; i++) { // 检查所有结点,把集合号是 q 的改为 p
            if (fa[i] == q)
                fa[i] = p; // a 的集合号赋值给 b 集合号
        }
        return 1;
    }

    // 求最小生成树
    static int Kruskal(int n) {
        int ans = 0;
        Collections.sort(edgeList);
        for (int i = 0; i < m; i++)
            if (Merge(edgeList.get(i).u, edgeList.get(i).v) == 1) {
                ans += edgeList.get(i).w;
                n--;
                if (n == 1)//n-1次合并算法结束
                    return ans;
            }
        return 0;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        Init(n);
        for (int i = 1; i <= m; i++) {
            e[i].u = scanner.nextInt();
            e[i].v = scanner.nextInt();
            e[i].w = scanner.nextInt();
            edgeList.add(e[i]);
        }
        System.out.println("最小的花费是:" + Kruskal(n));
    }
}

class Edge implements Comparable {
    int u;
    int w;
    int v;

    @Override
    public int compareTo(Object o) {
        if (this.w > ((Edge) o).w) {
            return 1;
        } else if (this.w == ((Edge) o).w) {
            return 0;
        } else {
            return -1;
        }
    }
}

三、测试

绿色为输入,白色为输出。

到此这篇关于Java实现Kruskal算法的示例代码的文章就介绍到这了,更多相关Java Kruskal算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 浅谈算法之最小生成树Kruskal的Python实现

    目录 一.前言 二.树是什么 三.从图到树 四.解决生成问题 五.从生成树到最小生成树 六.实际问题与代码实现 七.结尾 一.前言 我们先不讲算法的原理,也不讲一些七七八八的概念,因为对于初学者来说,看到这些术语和概念往往会很头疼.头疼也是正常的,因为无端突然出现这么多信息,都不知道它们是怎么来的,也不知道这些信息有什么用,自然就会觉得头疼.这也是很多人学习算法热情很高,但是最后又被劝退的原因. 我们先不讲什么叫生成树,怎么生成树,有向图.无向图这些,先简单点,从最基本的内容开始,完整地将这个算

  • C++使用Kruskal和Prim算法实现最小生成树

    很久以前就学过最小生成树之Kruskal和Prim算法,这两个算法很容易理解,但实现起来并不那么容易.最近学习了并查集算法,得知并查集可以用于实现上述两个算法后,我自己动手实现了最小生成树算法. 宏观上讲,Kruskal算法就是一个合并的过程,而Prim算法是一个吞并的过程,另外在Prim算法中还用到了一种数据结构--优先级队列,用于动态排序.由于这两个算法很容易理解,在此不再赘述.接下来给出我的源代码. 输入 第一行包含两个整数n和m,n表示图中结点个数,m表示图中边的条数:接下来m行,每一行

  • Java实现Dijkstra算法的示例代码

    目录 一 问题描述 二 实现 三 测试 一 问题描述 小明为位置1,求他到其他各顶点的距离. 二 实现 package graph.dijkstra; import java.util.Scanner; import java.util.Stack; public class Dijkstra { static final int MaxVnum = 100; // 顶点数最大值 static final int INF = 0x3f3f3f3f; //无穷大 static final int

  • 详解Java Bellman-Ford算法原理及实现

    目录 一 点睛 二 算法步骤 三 算法实现 四 测试 一 点睛 如果遇到负权边,则在没有负环(回路的权值之和为负)存在时,可以采用 Bellman-Ford 算法求解最短路径.该算法的优点是变的权值可以是负数.实现简单,缺点是时间复杂度过高.但是该算法可以进行若干种优化,以提高效率. Bellman-Ford 算法与 Dijkstra 算法类似,都是以松弛操作作为基础.Dijkstra 算法以贪心法选取未被处理的具有最小权值的节点,然后对其进行松弛操作:而 Bellman-Ford 算法对所有边

  • Java实现Floyd算法的示例代码

    目录 一 问题描述 二 代码 三 实现 一 问题描述 求节点0到节点2的最短路径. 二 代码 package graph.floyd; import java.util.Scanner; public class Floyd { static final int MaxVnum = 100; // 顶点数最大值 static final int INF = 0x3f3f3f3f; //无穷大 static final int dist[][] = new int[MaxVnum][MaxVnum

  • python最小生成树kruskal与prim算法详解

    kruskal算法基本思路:先对边按权重从小到大排序,先选取权重最小的一条边,如果该边的两个节点均为不同的分量,则加入到最小生成树,否则计算下一条边,直到遍历完所有的边. prim算法基本思路:所有节点分成两个group,一个为已经选取的selected_node(为list类型),一个为candidate_node,首先任取一个节点加入到selected_node,然后遍历头节点在selected_node,尾节点在candidate_node的边,选取符合这个条件的边里面权重最小的边,加入到

  • Java实现Kruskal算法的示例代码

    目录 介绍 一.构建后的图 二.代码 三.测试 介绍 构造最小生成树还有一种算法,即 Kruskal 算法:设图 G=(V,E)是无向连通带权图,V={1,2,...n};设最小生成树 T=(V,TE),该树的初始状态只有 n 个节点而无边的非连通图T=(V,{}),Kruskal 算法将这n 个节点看成 n 个孤立的连通分支.它首先将所有边都按权值从小到大排序,然后值要在 T 中选的边数不到 n-1,就做这样贪心选择:在边集 E 中选择权值最小的边(i,j),如果将边(i,j)加入集合 TE

  • Java实现查找算法的示例代码(二分查找、插值查找、斐波那契查找)

    目录 1.查找概述 2.顺序查找 3.二分查找 3.1 二分查找概述 3.2 二分查找实现 4.插值查找 4.1 插值查找概述 4.2 插值查找实现 5.斐波那契查找 5.1 斐波那契查找概述 5.2 斐波那契查找实现 5.3 总结 1.查找概述 查找表: 所有需要被查的数据所在的集合,我们给它一个统称叫查找表.查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合. 查找(Searching): 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录).

  • Java实现雪花算法的示例代码

    一.介绍 SnowFlow算法是Twitter推出的分布式id生成算法,主要核心思想就是利用64bit的long类型的数字作为全局的id.在分布式系统中经常应用到,并且,在id中加入了时间戳的概念,基本上保持不重复,并且持续一种向上增加的方式. 在这64bit中,其中``第一个bit是不用的,然后用其中的41个bit作为毫秒数,用10bit作为工作机器id,12bit`作为序列号.具体如下图所示: 第一个部分:0,这个是个符号位,因为在二进制中第一个bit如果是1的话,那么都是负数,但是我们生成

  • Java实现抽奖算法的示例代码

    目录 一.题目描述 二.解题思路 三.代码详解 四.优化抽奖算法 解题思路 代码详解 一.题目描述 题目: 小虚竹为了给粉丝送福利,决定在参与学习打卡活动的粉丝中抽一位幸运粉丝,送份小礼物.为了公平,要保证抽奖过程是随机的. 二.解题思路 1.把参与的人员加到集合中 2.使用Random对象获取随机数 3.把随机数当下标,获取集合中的幸运用户 三.代码详解 public class Basics28 { public static void main(String[] args) { List<

  • Java实现8种排序算法的示例代码

    冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <

  • JAVA用递归实现全排列算法的示例代码

    求一个n阶行列式,一个比较简单的方法就是使用全排列的方法,那么简述以下全排列算法的递归实现. 首先举一个简单的例子说明算法的原理,既然是递归,首先说明一下出口条件.以[1, 2]为例 首先展示一下主要代码(完整代码在后面),然后简述 //对数组array从索引为start到最后的元素进行全排列 public void perm(int[]array,int start) { if(start==array.length) { //出口条件 for(int i=0;i<array.length;i

  • Java实现基本排序算法的示例代码

    目录 1. 概述 2. 插入排序 2.1 直接插入排序 2.2 希尔排序(缩小增量排序) 3. 选择排序 3.1 直接选择排序 3.2 堆排序 4. 交换排序 4.1 冒泡排序 4.2 快速排序 5. 归并排序 6. 计数排序(非比较类型的排序) 7. 排序算法总结 1. 概述 排序概念:就是将一串记录按照其中某个或某些关键字的大小,递增或递减的排列起来的操作. 稳定性:通俗的将就是数据元素不发生有间隔的交换,例如: 内部排序:数据元素全部放在内存中的排序 外部排序:数据元素太多不能一次加载到内

  • Java实现拓扑排序算法的示例代码

    目录 拓扑排序原理 1.点睛 2.拓扑排序 3.算法步骤 4.图解 拓扑排序算法实现 1.拓扑图 2.实现代码 3.测试 拓扑排序原理 1.点睛 一个无环的有向图被称为有向无环图.有向无环图是描述一个工程.计划.生产.系统等流程的有效工具.一个大工程可分为若干子工程(活动),活动之间通常有一定的约束,例如先做什么活动,有什么活动完成后才可以开始下一个活动. 用节点表示活动,用弧表示活动之间的优先关系的有向图,被称为 AOV 网. 在 AOV 网中,若从节点 i 到节点 j 存在一条有向路径,则称

随机推荐