※ [本文转录自 java 看板] 作者: qrtt1 (愚人) 看板: java 标题: Re: [请益] 如何在有上下阶层的资料结构中寻找共同 … 时间: Fri Mar 30 20:25:33 2007 ※ 引述《popcorn5368 (小宇)》之铭言： : ※ [本文转录自 MATLAB 看板] : 作者: popcorn5368 (小宇) 看板: MATLAB : 标题: [请益] 如何在有上下阶层的资料结构中寻找共同的祖先节点 : 时间: Fri Mar 30 16:17:15 2007 : 在一个有分上下阶层的类似树状的结构,且 : (1)此结构有cycle : (2) 一个节点可属於多个父节点 : 求:给予多个节点,求这些节点的共同的祖先节点中,层级最低者 : 问题: : 若是使用java实作,有人有较有效率的作法吗?或是可以使用哪些物件 : 减少coding的困难度?(驻:真实的结构很大,也可能会给予上百个点求解) : 我所预到的困难: : 原先想采用找出每个所给予节点,其所属的所有上层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 最呆的方法往上早直到没有上面为止 A 往上找 {X, Y} A, X 往上找 {X, W, Z, Y} A, X, Y 往上找 {X, W, Z,Y, Z} <--> 如果是用不重覆的容器, Z就不会出现2次 B 往上找 {A} ... 重复找 A 的步骤 B {A, X, W, Y, Z} ================================ A: {X, W, Z, Y} B: {A, X, W, Y, Z} H: {W, Z} J: {H, W, Z} ================================ 取交集 {W, Z} 算 W, Z 的高度? 不懂层次最低怎麽定义，树只有定义高度的算法 您想要算得更快，要用点 DP 的技巧重复使用已经算到的结果 加油噜 :P --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 125.232.233.159 -- 侃侃长论鲜窒碍 首页：http://www.psmonkey.idv.tw 众目睽睽无心颤 Blog：http://ps-think.blogspot.com 茕居少聊常人事 杀头容易告白难 欢迎参观 Java 版（@ptt.cc） \囧/ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.228.193.189