PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[請益] 如何在有上下階層的資料結構中尋找共同 …

看板Prob_Solve (計算數學 Problem Solving)作者 (小宇)時間17年前 (2007/03/30 21:06), 編輯推噓10(10推 0噓 5→)
留言15則, 4人參與, 最新討論串1/3 (看更多)
※ [本文轉錄自 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)
推
03/31 07:23, , 1F
麻煩請不要一直 cp
03/31 07:23, 1F
推
03/31 07:32, , 2F
你的 cycle 是指, 一直往父節點連最後會回到自己嗎?
03/31 07:32, 2F
推
03/31 07:32, , 3F
如果不是, 這種 case 似乎不適合叫 "cycle", 只能說
03/31 07:32, 3F
推
03/31 07:33, , 4F
不是 tree
03/31 07:33, 4F
推
03/31 07:34, , 5F
如果是這樣, 就先跑一遍決定出 level
03/31 07:34, 5F
推
03/31 07:35, , 6F
然後再用變形的"逆" bfs 找最小共同祖先
03/31 07:35, 6F
推
03/31 09:46, , 7F
重點是他怎麼建這個 structure，然後分辨上下吧 @_@
03/31 09:46, 7F
推
03/31 10:29, , 8F
找level似乎是一個方法,但是因為有cycle
03/31 10:29, 8F
→
03/31 10:30, , 9F
有可能一個節點有多個level
03/31 10:30, 9F
→
03/31 10:31, , 10F
這個結構是有cycle的DAG(directed acyclic graph)
03/31 10:31, 10F
→
03/31 10:33, , 11F
抱歉喔...因為發文及轉錄後...很少人回,所以希望能獲넠
03/31 10:33, 11F
→
03/31 10:34, , 12F
得多點意見.....所以才.....
03/31 10:34, 12F
推
03/31 11:09, , 13F
DAG 就是沒有 cycle, 我想你的意思是, child 可以經不同
03/31 11:09, 13F
→
03/31 11:10, , 14F
path 逆推回 共同的 parent ?
03/31 11:10, 14F
推
03/31 11:19, , 15F
是的,且一個節點可屬於多個父節點
03/31 11:19, 15F
‣ 更多 popcorn5368 的文章
文章代碼(AID): #163Gjmhz (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 popcorn5368 的文章
文章代碼(AID): #163Gjmhz (Prob_Solve)