数据结构第二季 Day09 图 拓扑排序、最小生成树、prim算

一、 拓扑排序（TopologicalSort）

1、一句话概括什么是 AOV 网？AOV 网必须是有向无环图吗？

• AOV网(Activity On Vertex Network)：以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为 AOV 网。
• 标准的 AOV 网必须是一个有向无环图（Directed Acyclic Graph，简称 DAG）

image.png

2、什么是前驱活动？什么是拓扑排序？

• 前驱活动：有向边起点的活动称为终点的前驱活动
• 拓扑排序：AOV 网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面

image.png

3、拓扑排序的核心思路 - 卡恩算法（最重要）？

image.png

4、我们在实际排序中，肯定不能把图结构破坏，那么怎么办？拓扑排序的代码实现思路？

• 另外建立一张表，存储每个顶点的入度

  
  image.png

5、拓扑排序的代码实现？

    public List<V> topologicalSort() {
        List<V> list = new ArrayList<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        Map<Vertex<V, E>, Integer> ins = new HashMap<>();
        // 初始化（将度为0的节点都放入队列）
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            int in = vertex.inEdges.size();
            if (in == 0) {
                queue.offer(vertex);
            } else {
                ins.put(vertex, in);
            }
        });

        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            // 放入返回结果中
            list.add(vertex.value);

            for (Edge<V, E> edge : vertex.outEdges) {
                int toIn = ins.get(edge.to) - 1;
                if (toIn == 0) {
                    queue.offer(edge.to);
                } else {
                    ins.put(edge.to, toIn);
                }
            }
        }

        return list;
    }

二、 生成树、最小生成树

1、什么是生成树？

• 生成树(Spinning Tree)，也称为支撑树
• 连通图的极小连通子图，它含有图中全部的 n 个顶点，恰好只有 n-1 条边
• 由下图可见，一个连通图的极小连通图可能有很多个

image.png

2、什么是最小生成树？

• 最小生成树(Minimum Spanning Tree)：是所有生成树中，总权值最小的那颗

image.png

3、最小生成树有什么作用？（至少说一点）

• 多个城市铺设光缆，如何费用最低

image.png

4、求最小生成树有 2 个经典算法，分别是什么？

• Prim
• Kruskal

5、什么是切分定理？

• 切分定理：给定任意切分，横切边中权值最小的边必然属于最小生成树。

image.png

6、Prim 算法执行过程？（要能理解并口述）

image.png
image.png
image.png