如何遍歷具有特定屬性的樹

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狀態，然後嘗試添加新邊，而不是重複完整的連通性測試。

根據具體如何定義路徑，您可能會說，該路徑的擴展將永遠不會包含使用頂點子集的邊 - 例如目前爲止位於路徑內部的頂點。如果源自那些不可觸及的頂點的邊足以使圖形連通，那麼路徑的任何延伸都不能使其不連通。那麼至少你只需要計算不同路徑的數量。如果原始圖形是規則的，我希望找到一些動態編程遞歸，可以讓它們在沒有明確枚舉的情況下對它們進行計數。