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

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

看板Prob_Solve (計算數學 Problem Solving)作者PsMonkey (痞子軍團團長)時間17年前 (2007/03/31 18:51)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/3 (看更多)

※ [本文轉錄自 java 看板] 作者: qrtt1 (愚人) 看板: java 標題: Re: [請益] 如何在有上下階層的資料結構中尋找共同 … 時間: Fri Mar 30 20:25:33 2007 ※ 引述《popcorn5368 (小宇)》之銘言： : ※ [本文轉錄自 MATLAB 看板] : 作者: popcorn5368 (小宇) 看板: MATLAB : 標題: [請益] 如何在有上下階層的資料結構中尋找共同的祖先節點 : 時間: Fri Mar 30 16:17:15 2007 : 在一個有分上下階層的類似樹狀的結構,且 : (1)此結構有cycle : (2) 一個節點可屬於多個父節點 : 求:給予多個節點,求這些節點的共同的祖先節點中,層級最低者 : 問題: : 若是使用java實作,有人有較有效率的作法嗎?或是可以使用哪些物件 : 減少coding的困難度?(駐:真實的結構很大,也可能會給予上百個點求解) : 我所預到的困難: : 原先想採用找出每個所給予節點,其所屬的所有上層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 最呆的方法往上早直到沒有上面為止 A 往上找 {X, Y} A, X 往上找 {X, W, Z, Y} A, X, Y 往上找 {X, W, Z,Y, Z} <--> 如果是用不重覆的容器, Z就不會出現2次 B 往上找 {A} ... 重複找 A 的步驟 B {A, X, W, Y, Z} ================================ A: {X, W, Z, Y} B: {A, X, W, Y, Z} H: {W, Z} J: {H, W, Z} ================================ 取交集 {W, Z} 算 W, Z 的高度? 不懂層次最低怎麼定義，樹只有定義高度的算法您想要算得更快，要用點 DP 的技巧重複使用已經算到的結果加油嚕 :P -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.232.233.159 -- 侃侃長論鮮窒礙首頁：http://www.psmonkey.idv.tw 眾目睽睽無心顫 Blog：http://ps-think.blogspot.com 煢居少聊常人事殺頭容易告白難歡迎參觀 Java 版（@ptt.cc）精華區 \囧/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.193.189