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

Fw: [問題] 樹的同構 (同一個圖不同的骨架樹)

看板Prob_Solve (計算數學 Problem Solving)作者marada (十公里孵到大甲)時間7年前 (2017/03/26 17:15)推噓5(5推 0噓 0→)

留言5則, 2人參與討論串1/1

※ [本文轉錄自 C_and_CPP 看板 #1OrgZPb9 ] 作者: marada (十公里孵到大甲) 看板: C_and_CPP 標題: [問題] 樹的同構 (同一個圖不同的骨架樹) 時間: Sun Mar 26 01:28:53 2017 開發平台(Platform): (Ex: Win10, Linux, ...) win7 編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出) GCC code::blocks 問題(Question)：找正方體所有不同形狀的展開圖餵入的資料(Input)：無預期的正確結果(Expected Output)： 11種正方體的展開圖錯誤結果(Wrong Output)： 17種展開圖有很多同構的樹沒刪掉程式碼(Code)：(請善用置底文網頁, 記得排版) pastbin: http://pastebin.com/xWGFkDCq 共300多行 = =" main()有50行問題出在issave函式，issave可能重寫比較快 QQ (~100行) 補充說明(Supplement)：本魯只是會偷寫室友作業的外系生 (不過題不是作業，我也畢業了問同學不方便) 程式碼有任何問題歡迎開鞭例如白吃的命名 dfs函數的參數超多註解亂寫很髒的issave 到處copypaste來的程式碼..... 程式首先用普呂佛序列生出了 K6 所有骨架樹然後用issave刪掉同構的最後把相鄰矩陣轉成螢幕上的樣子印出來所以同一棵樹(一種展開圖)會經過三種型態: 1.普呂弗序列 prufer[] 1-D array 2.相鄰矩陣 int** adjmap 2-D array 3.ansMap int** mp2 2-D array 我是在(2)的地方用issave 判斷骨架樹同構然後爆了QQ 查了一下判斷同構好像只能用暴力法附上wiki連出去的論文: http://unfolding.apperceptual.com/ 不過這是超立方體的展開右上角3D models那連結會是我之後的目標先這樣想到什麼再用編輯補 *****************************編輯線*************************** 囧我發現我用錯名詞了不應該說是同構舉例: . . . . . . . . . . . . . .[5 . . . .[1[3[6[4 . . . .[2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . ---------------- 30 th map . . . . . . . . . . .[1[3 . . . . . .[2 . . . . . .[4[6 . . . . . .[5 . . . . . . . . . . . . . ---------------- 29 th map . . . .[5 . . . . . .[1[3 . . . . .[4[2 . . . . . .[6 . . . . . . . . . . . . . . . . . . . . . ---------------- 24 th map 這三個都是一直線可是形狀不一樣.... (以上是把"篩子"去掉的編號) 我是在(2)步驟弄一個mask[] 去置換點的編號可以想像是正方體換一個方向的maping 然後把邏輯弄得有些亂.... 然後謝謝版友的資料，正在啃 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.42.172 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1490462937.A.949.html