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

[popcorn5368 (小宇)]

在一個有分上下階層的類似樹狀的結構,且

(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:轉錄至看板 java                                     03/30 16:19

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.125.32.51
※ 編輯: popcorn5368     來自: 140.125.32.51        (03/30 16:47)
推 leicheong:如果child node之間有就child depth先做
→ leicheong:排序的話?
推 popcorn5368:沒有這種資訊耶
推 popcorn5368:且因為有cycle,難確定depth
※ popcorn5368:轉錄至看板 Prob_Solve                               03/30 21:06