假设我们想用图来表示分子,其中每个节点是一个原子,每个边是原子之间的连接。决定两个图(代表分子)是否相等的算法是什么?由于分子被表示出来,每个节点都需要一个属性来定义它是哪个分子(碳、氮、氧等)。
为了更简单,假设每个图都从同一根原子n分支,我们可以将其用作算法的起始节点。
n-x,n-y,n-z。其中n是根氮节点,x,y,z是图的其余部分。

最佳答案

我同意Joachim Isaksson's answer的观点,即一般情况——见鬼,甚至不太一般的情况——很难解决。但是我想提出一个策略来解决具有指定起始元素的分子树图的相对狭窄的情况。[请注意,这相当于Peter de Rivaz's answer这是在我编写此答案时发布的。]
首先,让我们定义一种形式或一种语言来描述一个分子图,这个分子图是唯一的——这个分子图只能形成一个字符串。这将允许我们比较两个字符串,以确定两个图是否相同,从而将您的问题归结为创建两个正确的字符串进行比较。(这种方法也比直接的图形比较算法更容易进行可视化调试。)我通常看到以H2O和H2SO4等形式描述的分子但这种方法并不能保持分子的成像特性,因此不能用于比较(水可能是水或其他一些非常奇怪的元素排列)所以让我们用类似于lisp的语言来描述分子,根据这些规则:
每个图(包括子图)以(开头,以)结尾
任何有子节点的节点A都是新图中列出的第一个节点,此图按特定顺序(稍后确定)列出在其父图中。
没有子节点的任何节点A都按特定顺序列在其父图中(稍后确定)
有了这些开始的规则,我们现在可以用更类似于图表的术语来描述H2O:
O是图形的根,因此它将启动一个新图形:(O)
HO的第一个子图,但它没有子图,因此它按原样列在父图中,而不是作为子图的开始:(OH)
HO的第二个子图,但它没有子图,因此它按原样列在父图中,而不是作为子图的开始:(OHH)
所以
变成(OHH)
在这种情况下,排序并不重要,因为这两个Hs是无子的,在元素上是等价的。
让我们尝试一种奇怪的,不合理的形式的水来测试这种方法:
O是图形的根,因此它将启动一个新图形:(O)
HO的第一个子。它有一个子对象,因此它将启动一个新图形:(O(H))
HH的第一个子图,但它没有子图,因此它按原样列在父图中,而不是作为子图的开始:(O(HH))
我们知道,到目前为止,我们的方法可以处理一些简单的情况,比如H2O,在这种情况下,排序并不重要,但是如果不一致地排序O元素,H2SO4就无法工作。在计算子图(如果它有子图)之前,不可能给子图赋予有意义的顺序,因此我们将添加一个要执行的最终规则:
每个图(包括子图)以S开头,以(结尾
任何有子节点的节点A都是新图中列出的第一个节点,此图按特定顺序列出在其父图中(请参见步骤4)
没有子节点的任何节点A都按特定顺序列在其父图中(请参见步骤4)
访问所有子节点并创建其子图(如果有的话)后,按字母顺序排列父节点中的子节点/子图
用这个新规则重新访问H2O会产生相同的输出,因为这两个)s在字母顺序上是等价的,并且它们没有子代。所以让我们试试硫酸:
H是图形的根,因此它将启动一个新图形:S
(S)O的第一个子它有子级,因此它会启动一个新的图形:S
“H”是(S[unsorted:](O))的第一个子它没有孩子。没有其他子项可处理,因此不需要在此级别进行排序:O
(S[unsorted:](OH))O的第二个子这个没有孩子:S
(S[unsorted:](OH)O)O的第三个子。它有子级,因此它会启动一个新的图形:S
“h”是(S[unsorted:](OH)O(O))的第一个子。它没有孩子没有其他子项可处理,因此不需要在此级别进行排序:O
(S[unsorted:](OH)O(OH))O的第四个孩子这个没有孩子:S
最后,按字母顺序对(S[unsorted:](OH)O(OH)O)的子图进行排序:S(注意,我在字母比较中对子图进行了特殊处理,但这不是必需的。)
最终结果是(S(OH)(OH)OO)
让我们试试硫酸的变化,看看它会产生什么请注意,这并不能证明该方法是好的,只是演示了图中的变化如何产生不同的结果。
(S(OH)(OH)OO)是图形的根,因此它将启动一个新图形:S
(S)O的第一个子它有子级,因此它会启动一个新图形:S
(S[unsorted:](O))是第一个孩子。它没有孩子。O
(S[unsorted:](O[unsorted:]O))是第二个孩子,没有孩子H
现在对(S[unsorted:](O[unsorted:]OH))的子对象进行排序:O
(S[unsorted:](OHO)O的第二个子。它有子级,因此它会启动一个新的图形:S
(S[unsorted:](O))是第一个孩子它没有孩子H
(S[unsorted:](OHO)(O[unsorted:]H))是第二个孩子,没有孩子O
现在对(S[unsorted:](OHO)(O[unsorted:]HO))的子对象进行排序:O
最后,将(S[unsorted:](OHO)(OHO))的子项按字母顺序排序:S
此硫酸((S(OHO)(OHO)))与前一个不同((S(OHO)(OHO)))。
我没有试图正式地证明这种方法是有效的,甚至没有试图正式地描述它,也没有试图解释广泛的分子细节,比如键计数等等。不过,至少,我希望这能鼓励您尝试解决图形比较问题。我认为这是可行的。

09-25 22:14