拓扑排序原理与解题套路 | 算法必看知识十九

简介: 拓扑排序其实就是图类问题当中的一个简单应用,它其实是有固定的实现方式的,我们只需要掌握这些实现方式中的算法思想,相信它不再是一个难题。

原文链接

image.png

什么是拓扑排序

其实最开始学习算法,听到拓扑排序这几个字我也是懵逼的,后来学着学着才慢慢知道是怎么一回事。关于 拓扑 这个词,在网上找到这么一段解释:

所谓“拓扑”就是把实体抽象成与其大小、形状无关的“点”,而把连接实体的线路抽象成“线”,进而以图的形式来表示这些点与线之间关系的方法,其目的在于研究这些点、线之间的相连关系。

表示点和线之间关系的图被称为拓扑结构图。

拓扑结构与几何结构属于两个不同的数学概念。

在几何结构中,我们要考察的是点、线之间的位置关系,或者说几何结构强调的是点与线所构成的形状及大小。如梯形、正方形、平行四边形及圆都属于不同的几何结构,但从拓扑结构的角度去看,由于点、线间的连接关系相同,从而具有相同的拓扑结构即环型结构。

也就是说,不同的几何结构可能具有相同的拓扑结构。

拓扑在计算机领域研究的就是图,既然是图,那就会有节点和边,节点表示的是现实生活中抽象的东西,边表示的是这些东西之间的关系。

仔细想想,其实现实生活中的很多东西都能够抽象成计算机世界当中的图。

比如说对于实际的地图,我们可以用节点表示岔路口,边表示岔路口之间的连线;人的朋友圈,我们用节点表示人,用边表示人与人之间的关系;再比如历史事件,我们用节点表示事件,用边表示事件之间的联系;不管是人或者事,只要找到了其对应的联系,往往都可以抽象成图。

拓扑排序解决的是依赖图问题。

依赖图表示的是节点的关系是有依赖性的,比如你要做事件 A,前提是你已经做了事件 B。除了 “先有鸡还是先有蛋” 这类问题,一般来说事件的依赖关系是单向的,因此我们都用 有向无环图 来表示依赖关系。

拓扑排序就是根据这些依赖来给出一个做事情,或者是事件的一个顺序。

举个例子,朋友来家里吃饭,你准备做饭,你要做饭,首先得买菜,买菜得去超市,去超市要出门搭车,因此这个顺序就是 出门搭车 -> 到超市 -> 买菜 -> 回家做饭。

当然我举的这个例子你不需要计算机的帮助也能很清楚地知道这个顺序,但是有些事情并不好直接看出来,比如常见的 “一个非常大的项目中,如何确定源代码文件的依赖关系,并给出相应的编译顺序?”。

我们要学的是一个解决一类问题的普适的方法,而不是学习怎么快速得到一个具体问题的结果,换句话说,在学习之中,思考过程往往比结果和答案更重要。

实现原理

和图相关的问题常见的算法就是搜索,深度和广度,拓扑排序也不例外,我们首先来看看稍微简单,好理解的广度优先搜索,先放上代码模版:

public List<...> bfsTopologicalSort() {
    // 边界条件检测
    if (...) {
        return true;
    }
    Map<..., List<...>> graph = new HashMap<>();
    // 构建图
    ...
    // 这里表示的是对于每个节点,其有多少前置条件(前置节点)
    int[] inDegree = new int[totalNodeNumber];

    // 根据图中节点的依赖关系去改变 inDegree 数组
    for (Entry.Map<..., List<...>> entry : graph.entrySet()) {
        ...
    }

    Queue<...> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; ++i) {
        if (inDegree[i] == 0) {
            queue.offer(...);
        } 
    }

    List<...> result = new ArrayList<...>();
    while (!queue.isEmpty()) {
        int cur = queue.poll();

        // 记录当前结果
        result.add(...);

        // 对于当前节点,解除对其下一层节点的限制
        for (... i : map.getOrDefault(cur, new ArrayList<...>())) {
            inDegree[i]--;
            if (inDegree[i] == 0) {
                queue.offer(...);
            }
        }
    }

    return result;
}

拓扑排序问题是基于图的算法,那么首先我们要做的就是将问题抽象为图。

这里我用了一个 HashMap 来表示图,其中 Key 表示的是具体的一个节点,Value 表示的是这个节点其下层节点,也就是 List 里面的节点依赖于当前节点,之所以这样表示依赖关系是为了我们后面实现的方便。

接下来我们会用一个 inDegree 数组来表示每个节点有多少个依赖的节点,选出那些不依赖任何节点的节点,这些节点应该被最先输出,按照一般的广度优先搜索思维,我们开一个队列,将这些没有依赖的节点放进去。

最后就是广度优先搜索的步骤,我们保证从队列里面出来的节点是当前没有依赖或者依赖已经被解除的节点,我们将这些节点输出,这个节点输出,其下一层节点的依赖就要相应的减少,我们改变 inDegree 数组中对应的值即可,如果改变后,对应节点没有任何依赖了,表明这个节点可以被输出了,就把它加进队列,等待被输出。

最后的最后就是输出我们得到的答案,但是这里要提醒的是,我们要考虑出现环的情况,就类似 “鸡生蛋,蛋生鸡” 的问题,比如 A 依赖于 B,B 也依赖于 A,这时我们是得不到答案的。

我们再来看看深度优先搜索,其思想和前面讲的广度优先搜索略微不同,我们不再需要 inDegree 数组了,而且我们需要去用另一种方式去判断图中是否存在环,先放上代码模版:

public ... dfsTopologicalSort() {
    // 边界条件检测
    if (...) {

    }

    Map<..., List<...>> graph = new HashMap<>();

    // 构建图
    ...

    boolean[] visited = new boolean[numCourses];
    boolean[] isLooped = new boolean[numCourses];

    List<...> result = new ArrayList<...>();
    for (int i = 0; i < totalNodeNumber; ++i) {                       
        if (!visited[i] && !dfs(result, graph, visited, isLooped, i)) {
            return new ArrayList<...>();
        }
    }

    return result;
}

private ... dfs(List<...> result,
                Map<..., List<...>>[] graph,
                boolean[] visited,
                boolean[] isLoop,
                ... curNode) {
    // 判断是否有环
    if (isLoop[curNode]) {
        return false;
    }

    isLoop[curNode] = true;

    // 遍历当前节点的前置节点,也就是依赖节点
    for (int i : graph.get(curNode) {
        if (visited[i]) {
            continue;
        }

        if (!dfs(graph, visited, isLoop, i)) {
            return false;
        }
    }

    isLoop[curNode] = false;

    // record answer
    result.add(curNode)
    visited[curNode] = true;

    return true;
}

有一点需要注意的是,构建图的时候,我们需要和之前的广度优先搜索反转一下,也就是这里的 Key 表示的是一个节点,Value 中存的是其所依赖的节点,这也是和我们的实现方式有关,我们需要用到递归,递归用到函数栈,先处理的函数(节点)后输出结果。

理解了上面这一点,下面就是用递归去解决这个深度优先搜索问题,但是有一点是我们需要用到两个 boolean 数组,一个(visited 数组)是记录我们访问过的节点,避免重复访问,另外一个是防止环的出现,怎么避免,深度优先搜索是沿着一条路径一直搜索下去,我们需要保证这一条路径不会经过某个节点两次,注意我这里说的是一条路径。

两种算法算是两种实现的方式,但是目的都是一样的,思想是类似的。

拓扑排序其实就是图类问题当中的一个简单应用,它其实是有固定的实现方式的,我们只需要掌握这些实现方式中的算法思想,相信它不再是一个难题。

我们做题不是为了训练我们的做题速度,编码能力,更重要的是学习算法里面的一种思考问题的方式和方法,这种先进的思想或者说是思维模式可以引领着我们朝计算机领域更广阔、更深层次的地方去。

--- END ---

作者 | P.yh
来源 | 五分钟学算法

相关文章
|
29天前
|
算法 容器
令牌桶算法原理及实现,图文详解
本文介绍令牌桶算法,一种常用的限流策略,通过恒定速率放入令牌,控制高并发场景下的流量,确保系统稳定运行。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
令牌桶算法原理及实现,图文详解
|
9天前
|
存储 人工智能 缓存
【AI系统】布局转换原理与算法
数据布局转换技术通过优化内存中数据的排布,提升程序执行效率,特别是对于缓存性能的影响显著。本文介绍了数据在内存中的排布方式,包括内存对齐、大小端存储等概念,并详细探讨了张量数据在内存中的排布,如行优先与列优先排布,以及在深度学习中常见的NCHW与NHWC两种数据布局方式。这些布局方式的选择直接影响到程序的性能,尤其是在GPU和CPU上的表现。此外,还讨论了连续与非连续张量的概念及其对性能的影响。
29 3
|
1月前
|
负载均衡 算法 应用服务中间件
5大负载均衡算法及原理,图解易懂!
本文详细介绍负载均衡的5大核心算法:轮询、加权轮询、随机、最少连接和源地址散列,帮助你深入理解分布式架构中的关键技术。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
5大负载均衡算法及原理,图解易懂!
|
22天前
|
缓存 算法 网络协议
OSPF的路由计算算法:原理与应用
OSPF的路由计算算法:原理与应用
35 4
|
22天前
|
存储 算法 网络协议
OSPF的SPF算法介绍:原理、实现与应用
OSPF的SPF算法介绍:原理、实现与应用
49 3
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
80 8
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
78 7
|
14天前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法及应用
探索人工智能中的强化学习:原理、算法及应用
|
14天前
|
机器学习/深度学习 人工智能 算法
探索人工智能中的强化学习:原理、算法与应用
探索人工智能中的强化学习:原理、算法与应用
|
7天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。