least commom ancestor in general graph
看板Prob_Solve (計算數學 Problem Solving)作者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
推
01/05 23:13, , 1F
01/05 23:13, 1F
→
01/06 07:27, , 2F
01/06 07:27, 2F
→
01/06 07:29, , 3F
01/06 07:29, 3F
→
01/06 07:29, , 4F
01/06 07:29, 4F
推
01/06 11:55, , 5F
01/06 11:55, 5F
→
01/06 11:56, , 6F
01/06 11:56, 6F
推
01/06 13:42, , 7F
01/06 13:42, 7F
→
01/06 17:10, , 8F
01/06 17:10, 8F
推
01/09 15:32, , 9F
01/09 15:32, 9F
→
01/09 15:33, , 10F
01/09 15:33, 10F
→
01/09 19:42, , 11F
01/09 19:42, 11F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
