PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [請益] 如何在有上下階層的資料結構中尋找共同 …

看板Prob_Solve (計算數學 Problem Solving)作者PsMonkey (痞子軍團團長)時間17年前 (2007/03/31 19:10)推噓5(5推 0噓 0→)

留言5則, 1人參與討論串3/3 (看更多)

※ 引述《popcorn5368 (小宇)》之銘言： : 在一個有分上下階層的類似樹狀的結構,且 : (1)此結構有cycle : (2) 一個節點可屬於多個父節點我覺得只要講第二條就可以了... 第一條講了反而混淆 : 求:給予多個節點,求這些節點的共同的祖先節點中,層級最低者 : 例: 如下圖,給予A,B,J,H,希望得到 X (結果應該有W及X,但X的層級最低) : : W Z : -----------|---- | : | | | : | ----|---- : | | | : | X Y : | | | : | ------------ --- --- ---- : | | | | | : | | A K : | | | : | | B : | | | : | | ----|---- : | | | | : | | C D : H | : | ----|---- : ---|--- | | : | | E F : I J : 推 PsMonkey:麻煩請不要一直 cp 03/31 07:23 : 推 march20:你的 cycle 是指, 一直往父節點連最後會回到自己嗎? 03/31 07:32 : 推 march20:如果不是, 這種 case 似乎不適合叫 "cycle", 只能說 03/31 07:32 : 推 march20:不是 tree 03/31 07:33 : 推 march20:如果是這樣, 就先跑一遍決定出 level 03/31 07:34 : 推 march20:然後再用變形的"逆" bfs 找最小共同祖先 03/31 07:35 : 推 PsMonkey:重點是他怎麼建這個 structure，然後分辨上下吧 @_@ 03/31 09:46 : 推 popcorn5368:找level似乎是一個方法,但是因為有cycle 03/31 10:29 : → popcorn5368:有可能一個節點有多個level 03/31 10:30 你終究得要給每個 node 一個 level 吧？不然你如何能說 node[x] 跟 node[y] 哪個層級高哪個層級低？以你提的例子，H 跟 A 就得同個 level 不是嗎？所以似乎版主大人的說法比較實際（會不會比列出所有的 node 找交集快，我就沒去算了）另外就是，如果有一個 node M，他的 parent 是 J 跟 E 那你預期得到的答案是啥？ : → popcorn5368:這個結構是有cycle的DAG(directed acyclic graph) 03/31 10:31 這句真的是... 亂七八糟 : → popcorn5368:抱歉喔...因為發文及轉錄後...很少人回,所以希望能獲넠 03/31 10:33 : → popcorn5368:得多點意見.....所以才..... 03/31 10:34 cp 就是 cp，沒啥好講的，Sysop 版一堆 cp 求情文章看了就煩我壓根不懂你幹麼 po 去 Java 版我還要聯絡好心的 qrtt1 把他的文章轉過來這裡統一彙整 : 推 ledia:DAG 就是沒有 cycle, 我想你的意思是, child 可以經不同 03/31 11:09 : → ledia:path 逆推回共同的 parent ? 03/31 11:10 : 推 popcorn5368:是的,且一個節點可屬於多個父節點 03/31 11:19 -- 侃侃長論鮮窒礙首頁：http://www.psmonkey.idv.tw 眾目睽睽無心顫 Blog：http://ps-think.blogspot.com 煢居少聊常人事殺頭容易告白難歡迎參觀 Java 版（@ptt.cc）精華區 \囧/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.193.189