作者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那連結會是我之後的目標
先這樣 想到什麼再用編輯補
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.42.172
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1490462937.A.949.html
1F：推 CoNsTaR: 是否錯版 03/26 08:19
2F：推 Clangpp: 這個應該是Prob_Solve版喔 03/26 12:45
※ marada:轉錄至看板 Prob_Solve 03/26 17:15
3F：→ marada: 其實除了標題的問題之外，我還有點想重構程式碼 03/26 17:46
4F：→ marada: 但不知道如何下手，這個部分發這個版應該沒問題吧? 03/26 17:47
5F：推 Clangpp: 當然可以啊xd 03/26 18:04
6F：推 CoNsTaR: 不過我很好奇 樹到底有沒有被定義過標準操作介面 03/27 04:21
7F：→ CoNsTaR: 同構是建立在已經定義好所有可能的操作的情況下的 03/27 04:21