轻松学懂图（中）——拓扑排序、Kruskal算法和Prim算法_prim和kruskal和拓扑王道

作者：小桥流水78 | 2024-08-21 05:25:37

踩

prim和kruskal和拓扑王道

轻松学懂图（中）——拓扑排序、Kruskal算法和Prim算法

概述

上一篇文章将图相关的常见概念大概讲了一遍，今天主要介绍图相关的算法，可能一下子不太能理解，我会尽量用大白话为大家讲解，请耐心将不是很明白的地方多看几遍。如果有不正确的地方，还请指出，一起进步。

下面，我们将开始正文

拓扑排序究竟是啥？

AOV网

在了解拓扑排序之前，首先需要知道AOV网（Activity On Vertex Network），它长成下面这样：

在这里插入图片描述

在AVO网中，顶点表示活动（Activity），边用来表示活动之间的先后顺序。不难看出，AOV网是一种有向无环图。

AOE网

与AOV网不同的是每条边都有权值，可以理解为完成某个活动的开销，例如，在上面的AOV网中，如果给每个边加上权值，那么就可以表示花费的时间
拓扑排序

在上面那个AOV网中，所有活动之间的关系都通过边表示出来了，如何把这些事情有条不紊的做完对你来说肯定都可以看出来，比如：去菜市场 --> 买菜 --> 买米 --> 做饭 --> 做菜 -->吃饭，这种顺序其实就是拓扑排序，并且也很容易发现的是，对于同一个AOV网拓扑排序的结果可能有多个。

但是，倘若这个AOV网有上百个活动，活动之间的先后顺序也错综复杂，此时我们想按照一定的顺序将如此多的事情做完并且也符合活动的先后顺序，此时就不能用肉眼去观察了，那样太费时间了，因此，就出现了拓扑排序算法，那么它是如何实现的呢？让我们先来分析一下我们之前的那个拓扑排序你就明白了，让我们来观察一下下图：

在这里插入图片描述

不知道你通过上图拓扑排序生成的过程是否发现了其中的规律：

在所有活动中选择一个没有被其他活动所指向的活动（也就是入度为0的点）
然后再删除掉该点所有的边，即指向其他活动的有向边
再重复1、2步骤

恭喜你，你已经学会了拓扑排序了！下面就是拓扑排序的部分代码：

	/**
     * 拓扑排序——（可用来判断有向图中是否有环）
     *
     * @return
     */
    @Override
    public List<V> topologicalSort() {
        // 记录遍历过的节点，也即拓扑排序的结果
        List<V> list = new ArrayList<>();
        // 队列
        Queue<Vertex<V, E>> queue = new LinkedList();
        // map映射，记录顶点的入度信息
        Map<Vertex<V, E>, Integer> map = new HashMap<>();

        // 初始化队列和map
        vertices.forEach((v, vertex) -> {
            // 入度
            int in = vertex.inEdges.size();
            // 将一开始入度为0的顶点放入队列，不为0的放入map中
            if (in == 0) {
                queue.offer(vertex);
            } else {
                map.put(vertex, in);
            }
        });
        
        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            list.add(vertex.value);
            // 更新它所指向的顶点的入度
            for (Edge<V, E> edge : vertex.outEdges) {
                // 顶点更新后的入度
                int in = map.get(edge.to) - 1;
                if (in == 0) {
                    // 放入队列中
                    queue.offer(edge.to);
                } else {
                    // 更新map中该顶点对应的入度
                    map.put(edge.to, in);
                }
            }
        }
        return list;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44