作者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/cn.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