关于递归算法的思考

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) 

听起来像这样。