作者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)