作者DJWS (...)
看板Prob_Solve
標題least commom ancestor in general graph
時間Thu Jan 5 14:51:14 2017
我想要定義有向圖的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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1483599077.A.AE0.html
1F：推 FRAXIS: 是不是可以先找 SCC 然後建成 DAG 再來找 LCA? 01/05 23:13
2F：→ DJWS: 可以呀 然後採用遞迴版DFS離開節點的逆序 01/06 07:27
3F：→ DJWS: 這樣就有LCA的功效了 但是我沒看過類似的東西 想問有沒有 01/06 07:29
4F：→ DJWS: 人看過 01/06 07:29
6F：→ FRAXIS: 但是我覺得這跟你的問題還是不太一樣就是了.. 01/06 11:56
7F：推 ZanFu5566: Euler tour? 01/06 13:42
8F：→ DJWS: 不太一樣 我想問的是圖上有環的LCA 01/06 17:10
9F：推 aaaaajack: 我覺得點順序還是要符合拓樸排序才合理吧(同SCC內隨意) 01/09 15:32
10F：→ aaaaajack: 不然假設x可到y但x比y大 y就直接被x吃掉了 01/09 15:33
11F：→ DJWS: 遞迴版DFS離開節點的逆序 --> 一般圖的拓樸順序 01/09 19:42