作者future1234 (future)
看板TransCSI
標題Re: [問題] 資料結構的back edge?
時間Fri Jun 20 22:07:53 2008
nontree edge
(back edge)
---- 3
| / \
| 4 5--- nontree edge
| | | | (back edge)
| 2 6 |
| | | |
---1 7--|
| |\
0 8 9
V: 0 1 2 3 4 5 6 7 8 9
dfn: 4 3 2 0 1 5 6 7 8 9
low: 4 0 0 0 0 5 5 5 8 9
"cross edge",指在graph中,不滿足ancestor-descendant的edge
重點是這個low,你手上投影片應該有這個公式:
low(u)=min{dfn(u),
min{low(w)|w is a child of u},
min{dfn(w)|(u,w) is a back edge}
上圖的這兩個邊是虛線喔, 沒連起來, 因為上圖要作DFS tree
E(1,3)跟E(7,5)這兩個back edge很重要,因為它會在上面這個公式
"min{dfn(w)|(u,w) is a back edge" , 這部分產生作用
EX:
low(2)=min{ 2, min{low(1)}, null} = 0
^^^^^^^^^^^
low(1)=min{ 3, min{low(4)}, 0} = 0
^^^
它由back edge找到vertex 1
,並知道dfn(3)=0
我也有疑問, 為什麼要找vertex 3當root
: 當中有的nontree edge
: 提到如果u是v的祖先或v是u的祖先
: 則稱此邊為back edge
: 那cross edge是指什麼呢??
: 然後back edge 是怎樣找出來的
: 我知道他要形成一個circle...
: 但是為什麼是那兩個點相連??(3跟1 & 5跟7)
: 最後一個問題是
: 算出來的low...到底意義是??
: 看了書，但是還是不懂...
: 非常感謝>"<
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.67.210.63
※ 編輯: future1234 來自: 203.67.210.63 (06/20 22:09)