如何避免递归函数中的循环（breadthfirst遍历）

Question

我在写一个递归的广度优先遍历网络。我遇到的问题是网络通常是这样的：

    1
   / \
  2   3
   \ /
    4
    |
    5

所以我的遍历从1开始，然后遍历到2，然后是3。下一站是前进到4，所以2遍历到4。在这之后，3遍历到4，突然我重复工作，因为两条线都试图遍历到5。在

我找到的解决方案是创建一个名为self.already_traversed的列表，每次遍历一个节点时，我都会将其附加到列表中。然后，当我从节点4遍历时，我检查以确保它还没有被遍历。在

这里的问题是我使用了一个实例变量来完成这个任务，所以我需要一种在第一次递归之前设置列表的方法，以及之后清理列表的方法。我目前的做法是：

^{2}$

当然，在使用它们的函数之外成为两个变量是很糟糕的。有没有更好的方法可以把它放到遍历函数中？在

---

以下是实际代码，尽管我知道代码有点密集：

def _traverse_all_nodes(self, root_authority, max_depth=6):
    """Recursively build a networkx graph

    Process is:
     - Work backwards through the authorities for self.cluster_end and all
       of its children.
     - For each authority, add it to a networkx graph, if:
        - it happened after self.cluster_start
        - it's in the Supreme Court
        - we haven't exceeded a max_depth of six cases.
        - we haven't already followed this path
    """
    g = networkx.Graph()
    if hasattr(self, 'already_traversed'):
        is_already_traversed = (root_authority.pk in self.visited_nodes)
    else:
        # First run. Create an empty list.
        self.already_traversed = []
        is_already_traversed = False

    is_past_max_depth = (max_depth <= 0)
    is_cluster_start_obj = (root_authority == self.cluster_start)
    blocking_conditions = [
        is_past_max_depth,
        is_cluster_start_obj,
        is_already_traversed,
    ]
    if not any(blocking_conditions):
        print "  No blocking conditions. Pressing on."
        self.visited_nodes.append(root_authority.pk)
        for authority in root_authority.authorities.filter(
                docket__court='scotus',
                date_filed__gte=self.cluster_start.date_filed):

            g.add_edge(root_authority.pk, authority.pk)
            # Combine our present graph with the result of the next
            # recursion
            g = networkx.compose(g, self._build_graph(
                authority,
                max_depth - 1,
            ))

    return g

def add_clusters(self):
    """Do the network analysis to add clusters to the model.

    Process is to:
     - Build a networkx graph
     - For all nodes in the graph, add them to self.clusters
    """
    self.already_traversed = []
    g = self._traverse_all_nodes(
        self.cluster_end,
        max_depth=6,
    )
    self.already_traversed = []

Answer 1

退房：

How do I pass a variable by reference?

其中包含一个如何通过引用跳过列表的示例。如果通过引用传递列表，则对函数的每次调用都将引用同一个列表。在