algorithm - 我无法逐步理解逻辑!有人能指出我正确的方向吗？

Question

任何人都可以帮助我逐步了解下面显示的程序的逻辑吗？我尝试使用 Python debugger .但这对我没有太大帮助。

我不明白以下内容:

• preorder_traversal()

  • 例如在yield (parent, root) 代码行；函数此时将这些值作为生成器返回给调用者，还是返回生成器然后继续进入 preorder_traversal() 函数？

  • 此外，当我试图围绕递归调用 到 preorder_traversal() 时，我的头脑完全融化了。有谁知道理解这一点的方法？就像真值表或类似的东西，我可以用笔和纸或记事本或其他任何东西手动逐步执行程序。我认为其中最复杂的部分是嵌套和递归。

• 我不理解 Node inside a Node inside a Node 等。或者将节点添加到列表的整个添加和边缘部分。

代码

class Node(object):
    """A simple digraph where each node knows about the other nodes
    it leads to.
    """
    def __init__(self, name):
        self.name = name
        self.connections = []
        return

    def add_edge(self, node):
        "Create an edge between this node and the other."
        self.connections.append(node)
        return

    def __iter__(self):
        return iter(self.connections)

def preorder_traversal(root, seen=None, parent=None):
    """Generator function to yield the edges via a preorder traversal."""
    if seen is None:
        seen = set()
    yield (parent, root)
    if root in seen:
        return
    seen.add(root)
    for node in root:
        for (parent, subnode) in preorder_traversal(node, seen, root):
            yield (parent, subnode)
    return

def show_edges(root):
    "Print all of the edges in the graph."
    for parent, child in preorder_traversal(root):
        if not parent:
            continue
        print '%5s -> %2s (%s)' % (parent.name, child.name, id(child))

# Set up the nodes.
root = Node('root')
a = Node('a')
b = Node('b')
c = Node('c')

# Add edges between them.
root.add_edge(a)
root.add_edge(b)
a.add_edge(b)
b.add_edge(a)
b.add_edge(c)
a.add_edge(a)

print 'ORIGINAL GRAPH:'
show_edges(root)

感谢您阅读本文。

Answer 1

至于yield运算符，yield 允许函数成为生成器，因此 lazy .对于这个特定的例子，不需要生成器，它的唯一好处是更好的可读性(即 for _ in _)。抽象地说，yield (parent, root) 是通过使用 next() 返回的对发电机的操作。然后，当再次调用next()时，生成器会继续动态执行函数中剩余的代码。

至于递归调用，这在执行任何类型的 graph traversal 时都很常见。 .此外，图表是 recursive data structure .

Here是了解图遍历的好资源。

下面是 preorder_traversal() 的略微修改版本(更易于阅读)，其中有一些注释:

def preorder_traversal(root, seen=set(), parent=None):
    """Generator function to yield the edges via a preorder traversal."""
    yield (parent, root)

    # avoid cycle
    if root not in seen:
        seen.add(root)

        # for each neighbor of the root
        for node in root:

            # for each (parent, neighbor) pair in the subgraph 
            # not containing the nodes already seen 
            for (parent, subnode) in preorder_traversal(node, seen, root):
                yield (parent, subnode)

为了演示 Python 生成器的惰性特性，请考虑自定义 irange() 生成器，其中 irange(n) == xrange(n+1):

def irange(limit):
    current_number = 0
    while current_number <= limit:
        yield current_number
        current_number += 1

如果你执行 a = irange(9999999999999999999999)，irange() 中的代码不会执行，直到 next() 被调用.

要了解生成器的递归，请考虑自定义 rrange() 生成器，其中 rrange(n) == reversed(irange(n)):

def rrange(limit):
    if limit >= 0:
        yield limit
        for num in rrange(limit - 1):
            yield num