※ [本文转录自 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 . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .