任何人都可以帮助我逐步了解下面显示的程序的逻辑吗?我尝试使用 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)
感谢您阅读本文。
最佳答案
至于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
关于algorithm - 我无法逐步理解逻辑!有人能指出我正确的方向吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45698255/