作者gianli (喔)
看板TransCSI
标题Re: [问题] DFS Tree之low值求法!?
时间Thu Feb 14 23:37:01 2008
※ 引述《axax (辣吹)》之铭言：
: http://0rz.tw/1c3zV
: http://0rz.tw/d63zk
: A B C D E F G H I J
: dfs 1 2 3 4 7 8 9 10 5 6
: low 1 1 1 1 2 7 7 2 3 3
: 图在上面
: low(x)=min{dfn(x),
: dfn(w), //w为x之後代
: dfn(u)} //u是x及其後代经过一个back edge到达之点
: 定义就是这三个取最小值
: 但是含意我看不太懂..囧
: 能否举例解释一下~隔了两年的笔记已经看不懂了~
: 先谢谢各位!!
举I来说
low(I) = min { dfn(I)=5 //dfs number
dfn(J)=6 //I的後代就是J
dfn(C)=3 //看tree他有个back edge(虚线)回到C点
所以最小值就是3
或举C来说他的後代有经过一个Back edge回到A LOW值就是A的dfn number
这样解释...不知道清不清楚 你参考看看罗
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 125.225.74.139