關於遞歸算法的思考

Question

我手邊有一個問題，可以說如下。

有兩個節點集合（在二部向圖），Type1和Type2。

對於TYPE1的圖形的每一個節點，我必須找出一種構造以這種方式一組：

令節點1爲type1的第一個節點。

在集合中添加node1。 對於節點1，找出通過源節點爲node1的邊連接的類型2的節點列表。 對於上面獲得的列表中的每個成員，找到類型1（不在集合中）的節點，該節點通過目標是edge2的節點連接。在集合中添加這些節點。 重新運行，直到該集合中沒有任何內容添加爲止。

迭代類型1的所有節點。

我的直覺是要走向一個遞歸實現，但我無法弄清楚什麼參數（困惑）。

有什麼建議嗎？

Answer 1

這聽起來像是你可以修改breadth first search算法（它可以實現使用隊列）。

Answer 2

由於它的指示，所以節點總共有一個訂單。

您可以使用深度優先搜索結構。

def visit(some_node, type_1_set): 
    assert node.type == 1 
    type_1_set.add(some_node) 
    for child in some_node.children: 
     if child.type == 2: 
      for grand_child in child.children: 
       if grant_child.type == 1: 
        visit(grand_child, type_1_set) 

聽起來像這樣。