Re: [請益] 如何在有上下階層的資料結構中尋找共同 …
※ 引述《popcorn5368 (小宇)》之銘言：
: 在一個有分上下階層的類似樹狀的結構,且
: (1)此結構有cycle
: (2) 一個節點可屬於多個父節點
: 求:給予多個節點,求這些節點的共同的祖先節點中,層級最低者
: 問題:
: 有人想得到比較有效率的演算法?
: (駐:真實的結構很大,也可能會給予上百個點求解)
: 我所預到的困難:
: 原先想採用找出每個所給予節點,其所屬的所有上層node
: ,然後再將這些所有的上層node的集合取交集,若是結果有多個再做判斷
: .....感覺這個做法超沒效率,而且自己要寫code。
這結構不該說是樹,因為它不是樹,而是有階層有循環的圖.
我們知道它一樣是由點集合與弧集合所構成.
每個點有個標籤標記其層級.
這圖與樹的差異,在於層級是由節點標籤決定,而不是由弧決定.
每個點可往上層尋找祖先,
因有循環的緣故,最遠若不是找到頂層節點,就是找到本身節點.
因此,基本的算法是:
對每個指定的點Xi
Qi <- 尋找祖先(Xi)
T <- 求交集節點(Q)
return 最低層節點(T)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.117.134.243
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
