一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 414|回复: 4
收起左侧

[树/链表/图] 关于Tarjan算法

[复制链接] |试试Instant~ |刷题, 树/链表/图
我的人缘0

分享帖子到朋友圈
ozox | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
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算法常用的思想,即使面试碰不到,搞懂它对于解决其他类型的图算法也是很有帮助的。

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

评分

参与人数 6大米 +8 收起 理由
liuwen + 2 给你点个赞!
abc99 + 2 给你点个赞!
Chunky + 1 赞一个
tony601818 + 1 赞一个
emilyusa + 1 赞一个
Fzyyy + 1 赞一个

查看全部评分


上一篇:刷题网最新高频题top100
下一篇:是不是在简历中加入做过的project比较好
我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (450)
 
 
0% (3)    👎
到现在还不懂这个,回头有空了研究一下。谢谢楼主
回复

使用道具 举报

我的人缘0
animax00 2020-5-24 02:07:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (36)
 
 
0% (0)    👎
发错贴子了...
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (455)
 
 
2% (12)    👎
亚麻oa之一...
回复

使用道具 举报

我的人缘0
 楼主| ozox 2020-5-24 03:09:21 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (17)
 
 
0% (0)    👎

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-7-15 00:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表