java如何实现最小高度树

发布时间:2022-01-17 14:25:56 作者:清风
来源:亿速云 阅读:117

这篇文章主要为大家展示了java如何实现最小高度树,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带大家一起来研究并学习一下“java如何实现最小高度树”这篇文章吧。

对于一个具有树特征的无向图,我们可选择任何一个节点作为根。图因此可以成为树,在所有可能的树中,具有最小高度的树被称为最小高度树。给出这样的一个图,写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点,标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表(每一个边都是一对标签)。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边, [0, 1]和 [1, 0] 是相同的,因此不会同时出现在 edges 里。

示例 1:

输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]         0         |         1        / \       2   3  输出: [1]

示例 2:

输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]      0  1  2       \ | /         3         |         4         |         5  输出: [3, 4]

说明:

1,根据树的定义,树是一个无向图,其中任何两个顶点只通过一条路径连接。换句话说,一个任何没有简单环路的连通图都是一棵树。

2,树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

答案:

 1public List<Integer> findMinHeightTrees(int n, int[][] edges) {
2    if (n == 1)
3        return Collections.singletonList(0);
4    List<Set<Integer>> adj = new ArrayList<>(n);
5    for (int i = 0; i < n; ++i)
6        adj.add(new HashSet<>());
7    for (int[] edge : edges) {
8        adj.get(edge[0]).add(edge[1]);
9        adj.get(edge[1]).add(edge[0]);
10    }
11    List<Integer> leaves = new ArrayList<>();
12    for (int i = 0; i < n; ++i)
13        if (adj.get(i).size() == 1)
14            leaves.add(i);
15    while (n > 2) {
16        n -= leaves.size();
17        List<Integer> newLeaves = new ArrayList<>();
18        for (int i : leaves) {
19            int j = adj.get(i).iterator().next();
20            adj.get(j).remove(i);
21            if (adj.get(j).size() == 1)
22                newLeaves.add(j);
23        }
24        leaves = newLeaves;
25    }
26    return leaves;
27}

解析:

这种解法比较简单,这里注意第19行,adj.get(i)获取的HashSet的size是等于1的。第20行会把叶子节点i给移除掉。我们先看个图更有助于理解

java如何实现最小高度树

比如这个,他是不停的把叶子节点去掉,直到最后剩下一个或2个节点的时候停止循环。

Java的优点是什么

1. 简单,只需理解基本的概念,就可以编写适合于各种情况的应用程序;2. 面向对象;3. 分布性,Java是面向网络的语言;4. 鲁棒性,java提供自动垃圾收集来进行内存管理,防止程序员在管理内存时容易产生的错误。;5. 安全性,用于网络、分布环境下的Java必须防止病毒的入侵。6. 体系结构中立,只要安装了Java运行时系统,就可在任意处理器上运行。7. 可移植性,Java可以方便地移植到网络上的不同机器。8.解释执行,Java解释器直接对Java字节码进行解释执行。

以上就是关于“java如何实现最小高度树”的内容,如果该文章对您有所帮助并觉得写得不错,劳请分享给您的好友一起学习新知识,若想了解更多相关知识内容,请多多关注亿速云行业资讯频道。

推荐阅读:
  1. c语言如何实现最小生成树
  2. 如何设置div+css最小高度

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java

上一篇:ZipperDown漏洞怎么处理

下一篇:vue如何用Echarts画柱状图

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》