我的编程空间,编程开发者的网络收藏夹
学习永远不晚

Java如何实现Kruskal算法

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

Java如何实现Kruskal算法

本文小编为大家详细介绍“Java如何实现Kruskal算法”,内容详细,步骤清晰,细节处理妥当,希望这篇“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,否则算法结束。

一、构建后的图

Java如何实现Kruskal算法

二、代码

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算法”文章已经介绍完毕,想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会,如果想了解更多相关内容的文章,欢迎关注编程网行业资讯频道。

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

Java如何实现Kruskal算法

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

Java如何实现Kruskal算法

本文小编为大家详细介绍“Java如何实现Kruskal算法”,内容详细,步骤清晰,细节处理妥当,希望这篇“Java如何实现Kruskal算法”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。介绍构造最小生成树还有一种
2023-07-02

Java如何实现Floyd算法

本篇内容主要讲解“Java如何实现Floyd算法”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Java如何实现Floyd算法”吧!一 问题描述求节点0到节点2的最短路径。二 代码package
2023-07-02

Java如何实现RSA算法

小编给大家分享一下Java如何实现RSA算法,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!以下是引用片段:package rsa; import java.mat
2023-06-03

Java MD5算法如何实现

本文小编为大家详细介绍“Java MD5算法如何实现”,内容详细,步骤清晰,细节处理妥当,希望这篇“Java MD5算法如何实现”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。MD5加密简介哈希算法又称散列算法,是
2023-07-02

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

目录一、前言二、树是什么三、从图到树四、解决生成问题五、从生成树到最小生成树六、实际问题与代码实现七、结尾一、前言 我们先不讲算法的原理,也不讲一些七七八八的概念,因为对于初学者来说,看到这些术语和概念往往会很头疼。头疼也是正常的,因为无端
2022-06-02

Java 中 DFS 算法该如何实现?(java dfs算法怎么实现)

在Java编程中,深度优先搜索(Depth-FirstSearch,简称DFS)是一种用于遍历或搜索图或树数据结构的算法。它从起始节点开始,尽可能深地探索图或树的分支,直到无法继续前进,然后回溯到最近的未完全探索的节点,继续探索其他分支。以下是在Java中实现DFS算法的详细步
Java 中 DFS 算法该如何实现?(java dfs算法怎么实现)
Java2024-12-16

如何实现 Java 寻路算法?(java寻路算法怎么实现)

在Java编程中,实现寻路算法是一个常见且有趣的任务。寻路算法用于在给定的环境中找到从一个起点到一个目标点的路径。以下是实现Java寻路算法的一般步骤:一、了解寻路算法的基本概念寻路算法有多种类型,如A*算法、Dijk
如何实现 Java 寻路算法?(java寻路算法怎么实现)
Java2024-12-19

C++怎么实现基于不相交集合的kruskal算法

这篇文章主要介绍“C++怎么实现基于不相交集合的kruskal算法”,在日常操作中,相信很多人在C++怎么实现基于不相交集合的kruskal算法问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C++怎么实现基于
2023-07-05

如何实现 Java 全排列算法?(java全排列算法怎么实现)

在Java编程中,全排列算法是一种常见且重要的算法。它用于生成给定元素集合的所有可能排列。本文将详细介绍如何在Java中实现全排列算法,并提供相应的代码示例。一、全排列算法的基本概念全排列是指将一个集合中的所有元素进行排
如何实现 Java 全排列算法?(java全排列算法怎么实现)
Java2024-12-17

如何在 Java 中实现斐波那契算法?(java如何实现斐波那契算法)

在Java编程中,实现斐波那契算法是一个经典的练习,它可以帮助我们理解递归和循环的概念。斐波那契数列是一个数列,其中每个数字都是前两个数字的和。数列的起始数字通常为0和1。以下是在Java中实现斐波那契算法的两种常见方法:递归和循环。一、递归实现斐
如何在 Java 中实现斐波那契算法?(java如何实现斐波那契算法)
Java2024-12-17

java算法如何实现红黑树

这篇文章主要介绍了java算法如何实现红黑树,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。红黑树定义红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计
2023-05-30

Java编程如何实现A*算法

这篇文章主要介绍了Java编程如何实现A*算法,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。本文实例代码结构:% % % % % % % % o o o o o % %
2023-05-30

Java如何实现决策树算法

小编给大家分享一下Java如何实现决策树算法,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!具体如下:决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法,
2023-05-30

Java算法如何实现全排列

本篇内容主要讲解“Java算法如何实现全排列”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Java算法如何实现全排列”吧!算法一基于递归与回溯实现。在排列1,2,3的时候,先由3向上回溯到2发现
2023-07-02

如何实现 Java 协同过滤算法?(java协同过滤算法怎么实现)

在Java开发中,协同过滤算法是一种常用的推荐系统算法,它通过分析用户的行为和偏好来推荐相关的物品或内容。以下是实现Java协同过滤算法的一般步骤:一、数据收集与预处理收集用户行为数据,如用户的浏览记录、购买
如何实现 Java 协同过滤算法?(java协同过滤算法怎么实现)
Java2024-12-20

java如何实现快速排序算法

这篇文章将为大家详细讲解有关java如何实现快速排序算法,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。快速排序算法使用的分治法策略来把一个序列分为两个子序列来实现排序的思路:1.从数列中挑出一个元素,称为
2023-06-02

java如何实现排列组合算法

这篇文章主要介绍java如何实现排列组合算法,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!java排列组合算法[@more@]import java.util.ArrayList;import java.util.L
2023-06-03

Java如何实现权重随机算法

这篇文章主要讲解了“Java如何实现权重随机算法”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Java如何实现权重随机算法”吧!目录应用场景本文目标算法详解权重比例Java 实现应用场景客户
2023-06-20

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录