60 分钟搞定 Tarjan 算法求解无向图的割点与桥

本人在学习 Tarjan 算法求解无向图的割点与桥的问题时,很快发现了一篇简洁易懂的文章。很顺利地了解算法的思路,并写出了“高效”的代码,此时内心飘过 —— So Easy。然而,当我翻开《算法竞赛进阶指南》这本书的有关篇章时,我发现其中经过精简优化的代码有几条语句让我不得其所。以至于,花了较多心思和时间来思考🤔这段真正高效的 Tarjan 算法的工作原理以及代码的编写。关于 Tarjan 算法,我将会写若干篇系列文章,来完整系统地介绍 Tarjan 算法的原理以及其主要解决的问题。而在本章我主要讲一个问题 —— 如何使用 Tarjan 算法求解无向图的割点与桥。在讲述问题之前,我们先来简单地了解下什么是 Tarjan 算法?Tarjan 算法Tarjan 算法是基于深度优先搜索的算法,用于求解图的连通性问题。Tarjan 算法可以在线性时间内求出无向图的割点与桥,进一步地可以求解无向图的... Read More

递归

递归递归是什么?递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法 。维基百科简单说,就是自身调用自身。为什么使用递归?往往面对一类问题时,如果它的规模足够小或者说达到既定的边界条件时,我们可以直接获取答案。但是,当这类问题的规模比较大时,却往往无法直接获取答案。那么,这个时候就可以通过“自身调用自身”的方式,来不断地减小问题的规模,直到问题的规模被缩减到足够小时,直接将答案返回上层的调用者,最终获取到原问题的解。如果将求解的过程逆过来,那么就是所谓的递推。通过这种方式,我们可以写出“优雅”的代码去解决规模比较大的问题。进而,避免了通过递推的方式,在每一次递推时产生的复杂的条件判断的问题。上文中提到经过递归调用,会不断地减小问题的规模,有些作者认为这是一种减治法。递归的特性自身调用自身在上文中,已经提到了这个特性,而且也非常好理解,不再赘述。... Read More

后缀数组(Suffix Array)

本文介绍后缀数组的定义与构建的过程。首先,文章介绍什么是后缀数组,随后讲解了最自然的朴素算法。为了引出更高效的算法,文章提及了倍增思想与基数排序的背景基础知识。接着,通过模拟演练的方式一步一步地演示如何创建后缀数组。将构建的抽象过程形象地展示出来,使读者更易理解。定义给定字符串,其所有后缀有。(6为字符串的长度)。如下所示S = "banana"s1 = "banana"s2 = "anana"s3 = "nana"s4 = "ana"s5 = "na"s6 = "a"后缀数组即为由构成的有序的(字典序升序排列的)字符串数组。vector<string> sa{"a", "ana", "anana", "banana", "na", "nana"};构建后缀数组的动态过程演示动画: https://visualgo.net/zh/suffixarra思路如何构建后缀数组?若字符串的长... Read More

树状数组(Binary Indexed Tree)

树状数组或二叉索引树(英语:Binary Indexed Tree),又以其发明者命名为Fenwick树。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和, 区间和。它可以以的时间得到任意前缀和,并同时支持在时间内支持动态单点值的修改。空间复杂度。摘自维基百科文章先介绍低位运算(lowbit)的基本知识,再提及如何将一个整数划分为个区间的运算过程,进而延展到如何将线性序列以树行结构进行存取,接着介绍了高级数据结构——树状数组的两个基本操作——查询前缀和与单点增加,最后介绍了树状数组的一个应用——求解逆序对数。lowbit(低位)运算定义为非负整数在二进制表示下“最低位的1及其后边所有的0”构成的数值。比如:,其二进制表示为 ,则其低位。公式如何计算一个整数中二进制表示下所有位是1的数值?比如,则其二进制表示下所有位是1的数值有:,。... Read More

动态规划与分治法的思考

如果一个问题具有最优子结构的性质,此外子问题具有重叠性质,那么可以采用自底向上的动态规划的思路进行求解。同时,往往可以用递归的方式自顶向地进行求解,即分治法。如果用分治法去求解这个问题时,能够利用备忘录法进行避免对于子问题的重复计算,那么其计算的效率可以和动态规划的计算效率相比。文章来源:胡小旭 =>动态规划与分治法的思考 Read More

分治法与回溯法的思考

共同的递归性质在广义上来说,所有递归的算法都属于分治法。无非是将问题分解成一个规模更小的问题,还是将问题分解成若干个,甚至和输入规模多项式级别的子问题。那么对于前者,有些作者称作是减治法,后者称作分治法。那么对于回溯法(以深度优先搜搜方式进行)来说,目前为止我见过的都是通过递归的形式来实现的,那么从这个意义上来讲,回溯算法就是分治法的一种。回溯状态的有无再说,之所以称作是回溯法,是因为在搜索的过程中需要回溯到问题的某个状态,所以这往往需要保存回溯时的一些状态属性。然而,分治法通常并不需要考虑回溯状态的保存。分解问题的规模分治法往往是将问题分解成若干个子问题的形式,然而回溯法往往是将问题分解成规模更小的一个子问题。由于分治法将问题分解成若干个子问题,故当前问题的解需要依赖于若干个子问题,也就是若干个搜索路径的解,所以重点在于如何合并子问题的解;而然回溯法问题规模就为1个,当前的搜索路径的问题... Read More