※ [本文转录自 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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1490462937.A.949.html

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: marada (118.160.41.100), 03/26/2017 17:15:53 ※ 编辑: marada (118.160.41.100), 03/26/2017 23:28:52