※ [本文轉錄自 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 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .