文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java如何实现Kruskal算法

2023-07-02 17:12

关注

本文小编为大家详细介绍“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

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯