Re: [問題] DFS Tree之low值求法!?
※ 引述《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
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：