[問題] 樹的同構 (同一個圖不同的骨架樹)
開發平台(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那連結會是我之後的目標
先這樣 想到什麼再用編輯補
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.42.172
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1490462937.A.949.html
推
03/26 08:19, , 1F
03/26 08:19, 1F
推
03/26 12:45, , 2F
03/26 12:45, 2F
※ marada:轉錄至看板 Prob_Solve 03/26 17:15
→
03/26 17:46, , 3F
03/26 17:46, 3F
→
03/26 17:47, , 4F
03/26 17:47, 4F
推
03/26 18:04, , 5F
03/26 18:04, 5F
推
03/27 04:21, , 6F
03/27 04:21, 6F
→
03/27 04:21, , 7F
03/27 04:21, 7F