python - 如何遍历具有特定属性的树

Question

我有一棵树，如下图所示。

• 红色表示它具有某种属性，未填充表示它没有。我想尽量减少 Red 检查。
  1. 如果 Red 则所有 Ancestors 也都是 Red(并且不应再次检查)。
  2. 如果 Not Red 则所有后代都是 Not Red。
• 树的深度是d。
• 树的宽度是n。

• 请注意，子节点的值大于父节点。

  • 示例:在下面的树中，
    • 节点 '0' 有 child [1, 2, 3],
    • 节点 '1' 有 child [2, 3],
    • 节点 '2' 有 child [3] 和
    • 节点“4”有 child [](没有 child )。

  • 因此 children 可以构造为:

    if vertex.depth > 0:
        vertex.children = [Vertex(parent=vertex, val=child_val, depth=vertex.depth-1, n=n) for child_val in xrange(self.val+1, n)]
    else:
        vertex.children = []
    

这是一个示例树:

我正在尝试计算 Red 节点的数量。树的深度和宽度都会很大。所以我想进行某种深度优先搜索，并另外使用上面的属性 1 和 2。

我如何设计一个算法来遍历那棵树？

PS:我标记了这个 [python]，但算法的任何概述都可以。

更新与背景

1. 我想尽量减少属性(property)检查。
2. 属性检查正在检查根据我的树的路径构建的二分图的连通性。示例:
   • 示例树中左下角的节点有路径 = [0, 1]。
   • 设二部图具有大小为r 和c 的集合R 和C。 (注意，树的宽度是 n=r*c)。
   • 从路径开始，我通过从完整图开始并删除路径中所有值的边 (x, y) 来到达图的边缘:x, y = divmod(值, c)。

属性检查的两条规则来自图的连通性:- 如果图连接的边 [a, b, c] 被移除，那么它也必须连接 [a, b] 被移除(规则 1)。- 如果图断开连接并移除边 [a, b, c]，则它也必须断开连接并移除额外的边 d [a, b, c, d](规则 2)。

更新2

所以我真正想做的是检查从 [0..n] 中挑选 d 个元素的所有组合。树结构有点帮助，但即使我得到了最佳的树遍历算法，我仍然会检查太多的组合。 (我刚才注意到了。)

让我解释一下。假设我需要检查 [4, 5](因此 4 和 5 如上所述从二分图中删除，但此处无关紧要。)。如果结果显示为“红色”，我的树将阻止我仅检查 [4]。那很好。但是，我还应该将 [5] 标记为不进行检查。

我怎样才能改变我的树的结构(也许是一个图？)以进一步减少我的检查次数？

Answer 1

使用删除收缩算法的变体在完整二部图 K_{r,c} 上评估 Tutte 多项式(在 (1,2) 处评估，给出生成子图的总数)。

一句话，思路就是对边任意排序，枚举生成树，统计，对于每棵生成树，有多少个大小为r + c + k的生成子图有那个最小生成树。生成树的枚举是递归执行的。如果图 G 恰好有一个顶点，则关联的生成子图的数量是该顶点选择 k 上的自循环数。否则，找到 G 中非自环的最小边并进行两次递归调用。第一个是在图 G/e 上，其中 e 是收缩的。第二个是在图 G-e 上，其中删除了 e，但前提是 G-e 是连通的。