关于Tarjan算法

LC1192 Tarjan Algorithm

昨天花了整整一个晚上，复习和理解了Tarjan算法。想当年上学的时候，这些算法都学过应该还实现过，但是年代久远，工作中鲜有碰到，也就慢慢的还给老师了，只是依稀记得这是一个很牛逼的图算法，要用到DFS，但一上手写代码，还是会卡壳。每当这个时候，非常的难受，明明一个教科书的算法，怎么就还不会写！没办法，调整心态，退后一步，好好复习。

Tarjan算法是Graph Algorithm里比较难但又是比较有美感的算法，算法本身是可以用来计算一个图的SCC。算法有很多应用，LC1192其实是比较简单的一个应用，因为不需要返回SCC，这要发现图的bridge，因此少了一些变量，但整个算法的核心思想是不变的。下面就总结一下这个算法的几个核心思想，希望对没有接触过或有疑惑的同学有帮助。这里先讨论对无向图的应用，Tarjan算法对有向图也是一样适用的。

先解释一下几个算法中用到的概率：
每个node的访问序号（可以认为是time stamp）id
每个node的最小可reach的访问序号 low，这个概念是算法的核心的核心，可以理解为要到达当前的node最早（最小）的那个node的id

核心思想：
DFS：这个不需要多解释，所有node访问以DFS来进行
当一个node第一次被访问的时候，他的id 和 low应该都是一样的，assign一个全局不断增加的值
对当前node的child依次进行访问，这时：
因为是无向图，要注意child是不是node的父亲节点，如果是，直接跳过
如果child已经访问过了，那么说明node可以从child访问，因此要把node的low更新成min(low[node], id[child])
如果child没有访问过，DFS（child）这里有一个环节要小心，就是DFS backtrack的时候要依次的update low[node] = min(low[node], low[child])


最后如果要返回所有的SCC，只需要遍历所有node的low，同一个SCC的node应该有一样的low。LC1192要求返回critical connections，只要在backtrack过程中check是否有id[cur] < low[child]情况，什么意思呢？就是说从child节点无法回到cur节点，否则上面的条件就不成立，因此，DFS过程中只有从cur到child的edge，而没有从child到cur的回路，因此这个edge就是critical connection。

Tarjan算法是图的经典算法之一，也属于比较难的算法，面试当中碰到的概率应该不大，但LC上也还是有公司会出这样的题目，而且有不少变形。另外，Tarjan的核心思想其实也是graph算法常用的思想，即使面试碰不到，搞懂它对于解决其他类型的图算法也是很有帮助的。

最后求加米，好多面经看不了，谢谢大家。

到现在还不懂这个，回头有空了研究一下。谢谢楼主

发错贴子了...

亚麻oa之一...

woshizu 发表于 2020-5-24 02:29
亚麻oa之一...

嗯，其实1192算是比较初级的Tarjan应用，用来做OA也算可以，但也属于偏难的题了，平时如果没有刷熟，用写出没有bug的代码，也不容易。