[請益] 如何在有上下階層的資料結構中尋找共同 …
在一個有分上下階層的類似樹狀的結構,且
(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)
推
03/30 16:55, , 1F
03/30 16:55, 1F
→
03/30 16:56, , 2F
03/30 16:56, 2F
推
03/30 19:49, , 3F
03/30 19:49, 3F
推
03/30 20:32, , 4F
03/30 20:32, 4F
※ popcorn5368:轉錄至看板 Prob_Solve 03/30 21:06
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
