计算科学 - 如何表示分子并比较相等性 - 吾爱随笔录

我最初在 StackOverflow 上问过这个问题，并被建议将它带到这里。

我已经看过这个关于内存中分子表示的问题，这对我来说很有意义（tl; dr将其表示为一个图，其中原子作为节点，键作为边）。但现在我的问题是：我们如何检查两个分子是否相等？这可以概括为我们如何检查（非循环）图的相等性？现在我们将忽略立体异构体和环状结构，例如第一个链接中给出的示例中的碳环。

这是我的问题的更详细描述：对于我的Molecule班级（截至目前），我打算有一个Atoms 数组和一个Bonds 数组。每个Bond将指向Atom两端的两个 s，并且将具有权重（即，该边缘中的化学键数）。换句话说，这将最类似于边缘列表图。我的第一个猜测是迭代一个分子中的Atoms 并尝试Atom根据Bond包含的 s 在另一个分子中找到对应的 s Atom，但这是一种相当幼稚的方法，而且复杂性似乎相当大（最好的猜测接近O（n！）。哎呀。）。

不管复杂性如何，这种方法似乎在大多数情况下都有效，但它似乎对某些分子不起作用。以这些为例（注意 OH 组的不同位置）：

    H   H   H   OH  H
    |   |   |   |   |
H - C - C - C - C - C - H (2-Pentanol)
    |   |   |   |   |
    H   H   H   H   H

    H   H   OH  H   H
    |   |   |   |   |
H - C - C - C - C - C - H (3-Pentanol)
    |   |   |   |   |
    H   H   H   H   H

如果我们检查这些分子，对于一个分子中的每个原子，在另一个分子中都有一个独特的相同元素原子，它具有相同数量和类型的键，但这两个分子显然不一样，它们也不是立体异构体（我现在不考虑）。相反，它们是结构异构体。有没有办法我们也可以检查这个相对结构？使用邻接列表而不是边缘列表会更容易吗？有没有我应该研究的图相等算法（最好是在 Java 中）？我已经研究了一点图规范化，但这似乎是 NP 难的。

查看Graph Isomorphism Problem Wikipedia 文章，似乎有界度的图对该问题具有多项式时间解。此外，平面图也有多项式解（即，边只在它们的端点相交）。在我看来，（至少大多数）分子满足这两个条件，那么这个问题的多项式时间解决方案是什么，或者我在哪里可以找到它？这次我的谷歌搜索让我失望了。