在我开始之前，在 CodeSkulptor 上运行代码！ http://www.codeskulptor.org/#user42_MYuqELNPFl_7.py我也希望评论能详细说明我所做的足够多的事情。如果您需要更多解释，请查看我的解释递归的方法在代码下面。
# If you don't want global variables, remove the indentation procedures
indent = -1
MAX_THRESHOLD = 10
INF = 1 << 63
def whitespace():
global indent
return '| ' * (indent)
class Node:
def __init__(self, name, num_repeats=INF):
self.name = name
self.num_repeats = num_repeats
def start(self):
global indent
if self.name.find('Sequence') != -1:
print whitespace()
indent += 1
print whitespace() + '%s_start' % self.name
def middle(self):
print whitespace() + '%s_middle' % self.name
def end(self):
global indent
print whitespace() + '%s_end' % self.name
if self.name.find('Sequence') != -1:
indent -= 1
print whitespace()
def dfs(graph, start):
visits = {}
frontier = [] # The stack that keeps track of nodes to visit
# Whenever we "visit" a node, increase its visit count
frontier.append((start, start.num_repeats))
visits[start] = visits.get(start, 0) + 1
while frontier:
# parent_repeat_count usually contains vertex.repeat_count
# But, it may contain a higher value if a repeat node is its ancestor
vertex, parent_repeat_count = frontier.pop()
# Special case which signifies the end
if parent_repeat_count == -1:
vertex.end()
# We're done with this vertex, clear visits so that
# if any other node calls us, we're still able to be called
visits[vertex] = 0
continue
# Special case which signifies the middle
if parent_repeat_count == -2:
vertex.middle()
continue
# Send the start message
vertex.start()
# Add the node's end state to the stack first
# So that it is executed last
frontier.append((vertex, -1))
# No more children, continue
# Because of the above line, the end method will
# still be executed
if vertex not in graph:
continue
## Uncomment the following line if you want to go left to right neighbor
#### graph[vertex].reverse()
for i, neighbor in enumerate(graph[vertex]):
# The repeat count should propagate amongst neighbors
# That is if the parent had a higher repeat count, use that instead
repeat_count = max(1, parent_repeat_count)
if neighbor.num_repeats != INF:
repeat_count = neighbor.num_repeats
# We've gone through at least one neighbor node
# Append this vertex's middle state to the stack
if i >= 1:
frontier.append((vertex, -2))
# If we've not visited the neighbor more times than we have to, visit it
if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
frontier.append((neighbor, repeat_count))
visits[neighbor] = visits.get(neighbor, 0) + 1
def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
visits[node] = visits.get(node, 0) + 1
node.start()
if node not in graph:
node.end()
return
for i, neighbor in enumerate(graph[node][::-1]):
repeat_count = max(1, parent_repeat_count)
if neighbor.num_repeats != INF:
repeat_count = neighbor.num_repeats
if i >= 1:
node.middle()
if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
dfs_rec(graph, neighbor, repeat_count, visits)
node.end()
visits[node] = 0
Sequence1 = Node('Sequence1')
MtxPushPop1 = Node('MtxPushPop1')
Rotate1 = Node('Rotate1')
Repeat1 = Node('Repeat1', 2)
Sequence2 = Node('Sequence2')
MtxPushPop2 = Node('MtxPushPop2')
Translate = Node('Translate')
Rotate2 = Node('Rotate2')
Rotate3 = Node('Rotate3')
Scale = Node('Scale')
Repeat2 = Node('Repeat2', 3)
Mesh = Node('Mesh')
cyclic_graph = {
Sequence1: [MtxPushPop1, Rotate1],
MtxPushPop1: [Sequence2],
Rotate1: [Repeat1],
Sequence2: [MtxPushPop2, Translate],
Repeat1: [Sequence1],
MtxPushPop2: [Rotate2],
Translate: [Rotate3],
Rotate2: [Scale],
Rotate3: [Repeat2],
Scale: [Mesh],
Repeat2: [Sequence2]
}
dfs(cyclic_graph, Sequence1)
print '-'*40
dfs_rec(cyclic_graph, Sequence1)
print '-'*40
dfs({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)
print '-'*40
dfs_rec({Sequence1: [Translate], Translate: [Sequence1]}, Sequence1)
可以找到输入和（格式良好且缩进的）输出here http://www.hastebin.com/etedihayay.py。如果你想看how我格式化了输出，请参考代码，也可以在 CodeSkulptor 上找到 http://www.codeskulptor.org/#user42_MYuqELNPFl_7.py.
对了，继续解释。更容易理解但效率低得多的递归解决方案如下：
def dfs_rec(graph, node, parent_repeat_count=INF, visits={}):
visits[node] = visits.get(node, 0) + 1
node.start()
if node not in graph:
node.end()
return
for i, neighbor in enumerate(graph[node][::-1]):
repeat_count = max(1, parent_repeat_count)
if neighbor.num_repeats != INF:
repeat_count = neighbor.num_repeats
if i >= 1:
node.middle()
if visits.get(neighbor, 0) < MAX_THRESHOLD and visits.get(neighbor, 0) < repeat_count:
dfs_rec(graph, neighbor, repeat_count, visits)
node.end()
visits[node] = 0
- 我们要做的第一件事是访问节点。我们通过增加字典中节点的访问次数来做到这一点。
- 然后我们提出
start节点的事件。
- 我们做一个简单的检查，看看该节点是否是无子节点（叶节点）。如果是的话，我们提高
end事件并返回。
- Now that we've established that the node has neighbors, we iterate through each neighbor. Side Note: I reverse the neighbor list (by using
graph[node][::-1]) in the recursive version to maintain the same order (right to left) of traversal of neighbors as in the iterative version.
- 对于每个邻居，我们首先计算重复计数。重复计数从祖先节点传播（继承），因此使用继承的重复计数unless the neighbor包含重复计数值。
- 我们提出
middle当前节点的事件（not邻居）如果正在处理第二个（或更大的）邻居。
- 如果邻居可以被访问，则邻居被访问。可访问性检查是通过检查邻居的访问次数是否小于 a) 来完成的
MAX_THRESHOLD次（对于伪无限循环）和 b) 上述计算的重复计数次数。
- 现在我们已经完成了这个节点；提高
end事件并清除哈希表中的访问。这样做是为了如果其他节点再次调用它，它不会导致可访问性检查失败和/或执行次数少于所需的次数。
