作者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:转录至看板 java 03/30 16:19
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.125.32.51
※ 编辑: popcorn5368 来自: 140.125.32.51 (03/30 16:47)
1F：推 leicheong:如果child node之间有就child depth先做 202.134.126.84 03/30 16:55
2F：→ leicheong:排序的话? 202.134.126.84 03/30 16:56
3F：推 popcorn5368:没有这种资讯耶 140.125.32.51 03/30 19:49
4F：推 popcorn5368:且因为有cycle,难确定depth 140.125.32.51 03/30 20:32
※ popcorn5368:转录至看板 Prob_Solve 03/30 21:06