在Python中比较两个树/图

Question

首先，我应该承认我对所有与图形相关的事情都很差。我的树是作为嵌套字典实现的，代表着未加权的马尔可夫链。

class Tree(object):
    def __init__(self, depth=6, seq=None):
        self.graph = dict()
        self.depth = depth
        if seq is not None:
            self.build(seq)

    def build(self, seq):
        for i in xrange(len(seq)):
            sseq = seq[i:i+self.depth]
            for j in xrange(len(sseq)):
                if j == 0:
                    if sseq[j] not in self.graph:
                        self.graph[sseq[j]] = dict()
                    nest_pointer = self.graph[sseq[j]]
                else:
                    if sseq[j] not in nest_pointer:
                        nest_pointer[sseq[j]] = dict()
                    nest_pointer = nest_pointer[sseq[j]]

我需要能够比较两个树，同时了解不同之处出现的深度，因为我要使用分级相似性评分系统，所以简单的递归深度优先搜索无法满足需求。

附注：

如果您可以为我的树提出更好的数据结构，我将非常感激。我选择字典以获得最大的时间性能。提前感谢您的帮助。

- Eli Korvigo

---

关于您的P.S.，SO上有很多建议可以帮助您实现一种不同的（我不敢说更好，因为我没有进行基准测试）树数据结构。请参见此处、此处或此处。 - Muttonchop

Answer 1

为什么不能使用递归DFS？只需将当前高度作为参数传递即可。我不太确定如何比较节点或子树，但以下伪代码可能有效，它记录所有两个节点比较不相等的时间（使用一些用户定义的比较nodes_different）。

（伪代码）：

def compare_trees_r(node1, node2, depth, result):
    if nodes_different(node1, node2):
        result.append(depth)
    for (pairs of children c1 and c2):
        compare_trees_r(c1, c2, depth + 1, result)

def compare_trees(t1, t2):
    result = []
    compare_trees_r(t1.graph, t2.graph, 0, result)
    return result

关于实际数据结构，如果不知道seq是什么，很难建议更合适的结构。但我强烈建议为节点创建一个类，这样可以更容易地理解代码。如果在优化前进行性能分析后发现它实际上造成了问题，那么再进行优化（毕竟过早优化是万恶之源）。

- Gretchen

---

嗯，这似乎是显而易见的，但我没有想到将深度参数添加到标准DFS算法中。现在感觉有点傻。不管怎样，这解决了问题。非常感谢你。 - Eli Korvigo