数据结构第二季 Day10 图 Kruskal算法

1、在 java 中如何优雅一些从 set 或者 map 中随机获取一个元素？

Iterator<Vertex<V, E>> it = vertices.values().iterator();
if (!it.hasNext()) return null;
Vertex<V, E> vertex = it.next();

2、从一堆数据中选最大值、最小值第一反应是什么？？？在 java 中自带二叉堆的数据结构是什么？

• 二叉堆、大顶堆、小顶堆
• java 中自带实现二叉堆功能的是优先级队列 PriorityQueue

3、Java 中一个要实现一个 interface 用什么关键字？一个类要继承一个 abstract class 用什么关键字？

• implement xxxInterface 实现接口
• extends xxxClass 继承类

4、Kruskal 算法 - 执行过程（能口述即可）？

• ①从剩余边（一开始是所有边）中选择权重最小的边
• ②如果取得的边，加入最小生成树数组中，如果不会构成环，就加入。否则就废弃
• ③重复①②操作，直到选出 n-1 条边

image.png
image.png

5、为什么会想到使用并查集解决这个问题？

• 有孤岛、连通、查是否同一集合等概念
• 所以就有点并查集的意思了

6、为什么会想到使用最小堆呢？

• 因为从一个不断剩余的数据中，拿出最小值的过程
• 是二叉堆最擅长的事情

7、自己尝试分析下两个算法的时间复杂度

• 最终分析时间复杂度都是 O(ElogE)

8、Kruskal 算法的代码实现

    private Set<EdgeInfo<V, E>> kruskal() {
        int vertexCount = verticesSize() - 1;
        if (vertexCount < 1) return null;
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator);
        UnionFind<Vertex<V, E>> unionFind = new UnionFind<>();
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            unionFind.makeSet(vertex);
        });
        while (!heap.isEmpty() && edgeInfos.size() < vertexCount) {
            Edge<V, E> edge = heap.remove();
            if (unionFind.isSame(edge.from, edge.to)) continue;
            unionFind.union(edge.from, edge.to);
            edgeInfos.add(edge.info());
        }

        return edgeInfos;
    }