作者popcorn5368 (小宇)
看板Prob_Solve
標題[請益] 如何在有上下階層的資料結構中尋找共同 …
時間Fri Mar 30 21:06:55 2007
※ [本文轉錄自 Programming 看板]
作者: popcorn5368 (小宇) 看板: Programming
標題: [請益] 如何在有上下階層的資料結構中尋找共同 …
時間: Fri Mar 30 16:46:58 2007
在一個有分上下階層的類似樹狀的結構,且
(1)此結構有cycle
(2) 一個節點可屬於多個父節點
求:給予多個節點,求這些節點的共同的祖先節點中,層級最低者
問題:
有人想得到比較有效率的演算法?
(駐:真實的結構很大,也可能會給予上百個點求解)
我所預到的困難:
原先想採用找出每個所給予節點,其所屬的所有上層node
,然後再將這些所有的上層node的集合取交集,若是結果有多個再做判斷
.....感覺這個做法超沒效率,而且自己要寫code。
例: 如下圖,給予A,B,J,H,希望得到 X (結果應該有W及X,但X的層級最低)
W Z
-----------|---- |
| | |
| ----|----
| | |
| X Y
| | |
| ------------ --- --- ----
| | | | |
| | A K
| | |
| | B
| | |
| | ----|----
| | | |
| | C D
H |
| ----|----
---|--- | |
| | E F
I J
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.125.32.51
※ 編輯: popcorn5368 來自: 140.125.32.51 (03/30 21:08)
推 PsMonkey:麻煩請不要一直 cp 03/31 07:23
推 march20:你的 cycle 是指, 一直往父節點連最後會回到自己嗎? 03/31 07:32
推 march20:如果不是, 這種 case 似乎不適合叫 "cycle", 只能說 03/31 07:32
推 march20:不是 tree 03/31 07:33
推 march20:如果是這樣, 就先跑一遍決定出 level 03/31 07:34
推 march20:然後再用變形的"逆" bfs 找最小共同祖先 03/31 07:35
推 PsMonkey:重點是他怎麼建這個 structure，然後分辨上下吧 @_@ 03/31 09:46
推 popcorn5368:找level似乎是一個方法,但是因為有cycle 03/31 10:29
→ popcorn5368:有可能一個節點有多個level 03/31 10:30
→ popcorn5368:這個結構是有cycle的DAG(directed acyclic graph) 03/31 10:31
→ popcorn5368:抱歉喔...因為發文及轉錄後...很少人回,所以希望能獲넠 03/31 10:33
→ popcorn5368:得多點意見.....所以才..... 03/31 10:34
推 ledia:DAG 就是沒有 cycle, 我想你的意思是, child 可以經不同 03/31 11:09
→ ledia:path 逆推回 共同的 parent ? 03/31 11:10
推 popcorn5368:是的,且一個節點可屬於多個父節點 03/31 11:19