作者popcorn5368 (小宇)
看板Prob_Solve
标题[请益] 如何在有上下阶层的资料结构中寻找共同 …
时间Fri Mar 30 21:06:55 2007
※ [本文转录自 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)
1F：推 PsMonkey:麻烦请不要一直 cp 03/31 07:23
2F：推 march20:你的 cycle 是指, 一直往父节点连最後会回到自己吗? 03/31 07:32
3F：推 march20:如果不是, 这种 case 似乎不适合叫 "cycle", 只能说 03/31 07:32
4F：推 march20:不是 tree 03/31 07:33
5F：推 march20:如果是这样, 就先跑一遍决定出 level 03/31 07:34
6F：推 march20:然後再用变形的"逆" bfs 找最小共同祖先 03/31 07:35
7F：推 PsMonkey:重点是他怎麽建这个 structure，然後分辨上下吧 @_@ 03/31 09:46
8F：推 popcorn5368:找level似乎是一个方法,但是因为有cycle 03/31 10:29
9F：→ popcorn5368:有可能一个节点有多个level 03/31 10:30
10F：→ popcorn5368:这个结构是有cycle的DAG(directed acyclic graph) 03/31 10:31
11F：→ popcorn5368:抱歉喔...因为发文及转录後...很少人回,所以希望能获넠 03/31 10:33
12F：→ popcorn5368:得多点意见.....所以才..... 03/31 10:34
13F：推 ledia:DAG 就是没有 cycle, 我想你的意思是, child 可以经不同 03/31 11:09
14F：→ ledia:path 逆推回 共同的 parent ? 03/31 11:10
15F：推 popcorn5368:是的,且一个节点可属於多个父节点 03/31 11:19