[請益] 如何在有上下階層的資料結構中尋找共同 …
※ [本文轉錄自 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
03/31 07:23, 1F
推
03/31 07:32, , 2F
03/31 07:32, 2F
推
03/31 07:32, , 3F
03/31 07:32, 3F
推
03/31 07:33, , 4F
03/31 07:33, 4F
推
03/31 07:34, , 5F
03/31 07:34, 5F
推
03/31 07:35, , 6F
03/31 07:35, 6F
推
03/31 09:46, , 7F
03/31 09:46, 7F
推
03/31 10:29, , 8F
03/31 10:29, 8F
→
03/31 10:30, , 9F
03/31 10:30, 9F
→
03/31 10:31, , 10F
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
03/31 11:09, 13F
→
03/31 11:10, , 14F
03/31 11:10, 14F
推
03/31 11:19, , 15F
03/31 11:19, 15F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：