作者ephesians (ephesians)
看板Programming
标题Re: [请益] 如何在有上下阶层的资料结构中寻找共同 …
时间Sat Mar 31 21:35:14 2007
※ 引述《popcorn5368 (小宇)》之铭言：
: 在一个有分上下阶层的类似树状的结构,且
: (1)此结构有cycle
: (2) 一个节点可属於多个父节点
: 求:给予多个节点,求这些节点的共同的祖先节点中,层级最低者
: 问题:
: 有人想得到比较有效率的演算法?
: (驻:真实的结构很大,也可能会给予上百个点求解)
: 我所预到的困难:
: 原先想采用找出每个所给予节点,其所属的所有上层node
: ,然後再将这些所有的上层node的集合取交集,若是结果有多个再做判断
: .....感觉这个做法超没效率,而且自己要写code。
这结构不该说是树,因为它不是树,而是有阶层有循环的图.
我们知道它一样是由点集合与弧集合所构成.
每个点有个标签标记其层级.
这图与树的差异,在於层级是由节点标签决定,而不是由弧决定.
每个点可往上层寻找祖先,
因有循环的缘故,最远若不是找到顶层节点,就是找到本身节点.
因此,基本的算法是:
对每个指定的点Xi
Qi <- 寻找祖先(Xi)
T <- 求交集节点(Q)
return 最低层节点(T)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.117.134.243