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

Question

我有一棵树，如下所示。

• 红色表示它有一定的属性，未填充表示它没有它。我想尽量减少Red检查。
  1. 如果Red比所有祖先也都Red（不应再次检查）。
  2. 如果Not Red比所有后裔都Not Red。
• 树的深度为d。
• 树的宽度是n。

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

  • 实施例：在下面的树中，
    • 节点 '0' 具有子[1，2，3]，
    • 节点 '1' 具有子[2，3]，
    • 节点'2'有孩子[3]和
    • 节点'4'有孩子[]（没有孩子）。

  • 因此孩子们可以设计为：

    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节点。树的深度和宽度都会很大。所以我想做一种Depth-First-Search，并且使用上面的属性1和2。

如何设计算法来遍历该树？

PS：我标记了这个[python]，但算法的任何轮廓都可以。

更新&背景

1. 我希望尽量减少财产检查。
2. 属性检查是检查从我树的路径构建的二分图的连通性。 例：
   • 在示例树中的左下节点具有路径 = [0，1]。
   • 让该二部图具有大小为r和c的集合R和C。（注意树的宽度是n=r*c）。
   • 从路径我通过从完整图开始，并删除路径中所有值的边（x，y），从而得到图的边：x, y = divmod(value, c)。

为属性检查来自图的连通的两个规则： - 如果图形与边[A，B，C]除去，那么它也必须有连接连接[ a，b]被删除（规则1）。 - 如果图形与边缘[a，b，c]断开连接，则它还必须与删除的附加边缘[a，b，c，d]（规则2）断开连接。

更新2

所以我真正想要做的是检查采摘d元素出来[0到n]的所有组合。树结构有点帮助，但即使我得到了最佳的树遍历算法，我仍然会检查太多的组合。 （我刚才注意到了。）

让我解释一下。假设我需要检查[4,5]（所以4和5从上面解释的二分图中删除，但在这里无关）。如果这出现“红色”，我的树会阻止我仅检查[4]。那很好。但是，我也应该检查[5]。

如何更改我的树的结构（可能是图形）以进一步最小化我的检查次数？

Answer 1

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

在一个句子中，思想是任意排序边缘，枚举生成树并计算每个生成树有多少个大小为r + c + k的生成子图具有该最小生成树。生成树的枚举是递归执行的。如果图G只有一个顶点，则相关生成子图的数量就是该顶点选择k上的自循环数。否则，找到G中不是自循环的最小边，并进行两次递归调用。第一个是在收缩e的图表G/e上。第二个是在G-e图上，其中e被删除，但只有在G-e被连接时。

Answer 2

Python已经足够接近伪代码。

class counter(object): 
    def __init__(self, ival = 0): 
     self.count = ival 

    def count_up(self): 
     self.count += 1 
     return self.count 

def old_walk_fun(ilist, func=None): 
    def old_walk_fun_helper(ilist, func=None, count=0): 
     tlist = [] 
     if(isinstance(ilist, list) and ilist): 
      for q in ilist: 
       tlist += old_walk_fun_helper(q, func, count+1) 
     else: 
      tlist = func(ilist) 
     return [tlist] if(count != 0) else tlist 
    if(func != None and hasattr(func, '__call__')): 
     return old_walk_fun_helper(ilist, func) 
    else: 
     return [] 

def walk_fun(ilist, func=None): 
    def walk_fun_helper(ilist, func=None, count=0): 
     tlist = [] 
     if(isinstance(ilist, list) and ilist): 
      if(ilist[0] == "Red"): # Only evaluate sub-branches if current level is Red 
       for q in ilist: 
        tlist += walk_fun_helper(q, func, count+1) 
     else: 
      tlist = func(ilist) 
     return [tlist] if(count != 0) else tlist 
    if(func != None and hasattr(func, '__call__')): 
     return walk_fun_helper(ilist, func) 
    else: 
     return [] 

# Crude tree structure, first element is always its colour; following elements are its children 
tree_list = \ 
["Red", 
    ["Red", 
     ["Red", 
      [] 
     ], 
     ["White", 
      [] 
     ], 
     ["White", 
      [] 
     ] 
    ], 
    ["White", 
     ["White", 
      [] 
     ], 
     ["White", 
      [] 
     ] 
    ], 
    ["Red", 
     [] 
    ] 
] 

red_counter = counter() 
eval_counter = counter() 
old_walk_fun(tree_list, lambda x: (red_counter.count_up(), eval_counter.count_up()) if(x == "Red") else eval_counter.count_up()) 
print "Unconditionally walking" 
print "Reds found: %d" % red_counter.count 
print "Evaluations made: %d" % eval_counter.count 
print "" 

red_counter = counter() 
eval_counter = counter() 
walk_fun(tree_list, lambda x: (red_counter.count_up(), eval_counter.count_up()) if(x == "Red") else eval_counter.count_up()) 
print "Selectively walking" 
print "Reds found: %d" % red_counter.count 
print "Evaluations made: %d" % eval_counter.count 
print "" 

Answer 3

您是否正在努力快速测试连通性？

要测试连通性图，我会按随机顺序选取边，并在看到连接它们的边时使用union-find合并顶点。如果图连接，我可以提前终止，并且我有一种连通性证书 - 连接两个先前未连接的顶点集的边。

当您在树上沿着/沿着二分图上的路径行走时，您正在从图中移除边。如果您移除的边缘不在连通性证书中，那么图形仍然必须连接 - 这看起来像是对我的快速检查。如果它位于连通性证书中，则可以在添加边之前恢复到union/find状态，然后尝试添加新边，而不是重复完整的连通性测试。

根据具体如何定义路径，您可能会说，该路径的扩展将永远不会包含使用顶点子集的边 - 例如目前为止位于路径内部的顶点。如果源自那些不可触及的顶点的边足以使图形连通，那么路径的任何延伸都不能使其不连通。那么至少你只需要计算不同路径的数量。如果原始图形是规则的，我希望找到一些动态编程递归，可以让它们在没有明确枚举的情况下对它们进行计数。