我想要一个数据结构，其中的键是多面体(无向 3 连通平面图；在我的例子中，它们可能主要是 <30 个顶点)，查找时等式是同构的。有没有一种有效的方法来实现这种映射？
我研究和思考了一些，但没有想出解决方案。看起来解决方案可能是其中之一
使用图形本身来查找数据的自定义数据结构
二叉搜索树(或其他类似的树)，需要明确定义的顺序。 (我怀疑这样的顺序是否存在)
一个散列表，需要一个好的散列。我无法立即想出比“顶点数”或类似的更好的方法。
如何进行高效查找？
最佳答案
每个多面体图都是平面的。平面图的同构问题是多项式时间。它没有一般图同构问题的未知但被认为是大的复杂性。虽然高效，但算法并不简单，并且依赖于一些相当深奥的数学来进行分析。
原始论文(据我所知)是 Hopcroft 1971 年的论文平面三重连通图同构的 N log N 算法，可从斯坦福大学获得，编号为 scanned copy .在这个问题上有很多工作要做。最近的一篇论文是 Algorithm and Experiments in Testing Planar Graphs for Isomorphism它具有对现有算法的大量引用以及它们之间运行时间的比较。本文介绍了一种算法，该算法为每个图形分配一个唯一代码，顺便还生成一个定义明确的排序。他们在那篇关于小图的论文中的最佳结果是 Brendan McKay 在 Practical Graph Isomorphism 中的算法。 .
关于data-structures - 以多面体图为键的映射，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13334516/