least commom ancestor in general graph

看板Prob_Solve作者DJWS (...)時間7年前 (2017/01/05 14:51)推噓4(4推 0噓 7→)

留言11則, 4人參與討論串1/1

我想要定義有向圖的LCA　　　　　　　　　　　G = (V,E) 1. 將圖上每一點定序，給予編號1到V 2. 一個點的父親，定義為入邊的另一個端點 fa(x) = {for all p: (p,x) in E} 3. 一個點的祖先，定義成父親0次至無限多次 anc(x) = {x, fa(x), fa(fa(x)), ...} 4. 兩個點的LCA，定義成兩家祖先的交集當中序號最大者 i 是不是就能定義有向圖的LCA？想請教板友是否看過類似的東西？ -- 最近發現dominator tree的演算法似乎可以用一般圖的LCA來解釋 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.7.138 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1483599077.A.AE0.html

推

FRAXIS

01/05 23:13, , 1^F

01/05 23:13, 1^F

→

DJWS

01/06 07:27, , 2^F

01/06 07:27, 2^F

→

DJWS

01/06 07:29, , 3^F

01/06 07:29, 3^F