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

愚人

2007-03-30 12:25:34 UTC

※ 引述《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