有没有办法在没有 class 属性或传递参数的情况下避免 revisiting/keep 跟踪访问节点的递归遍历？
Is there a way to avoid revisiting/keep track of visited nodes in recursive traversal without class attribute or passed parameter?
有没有办法在不传递已访问节点的“已访问”参数集（或将一个作为 class 属性或全局变量）的情况下递归地进行基于图的深度优先遍历？
维基百科上的伪代码似乎表明这是必要的。
我的代码（如下）在我将默认参数添加到给我的签名后工作。我根本不想弄乱函数签名，因为它是在单元测试中调用的。然而，默认参数被证明既有用又有害，但如果我必须使用递归，这是我能做到的唯一方法吗？
def dft_recursive(self, starting_vertex, visited = set()):
"""
Print each vertex in depth-first order
beginning from starting_vertex.
This should be done using recursion.
"""
print(starting_vertex)
visited.add(starting_vertex)
for neighbor in self.vertices[starting_vertex]:
if neighbor not in visited:
visited.add(neighbor)
self.dft_recursive(neighbor, visited)
为了证明这一点，让我们考虑以下 undirected graphs 图：
1。使用节点 Class 实例
实现节点的 Class，它存储 Visited 布尔标志状态本身。
另请注意，将 neighbours 存储在节点的 Class 本身中。
class Node:
def __init__(self, name):
self.name = name
self.neighbours = []
self.visited = False
self.previous_node = None # NOTE: This is just to show the printed result not really needed
def __str__(self):
return f'{self.name} can go to = {self.neighbours}, is Visited? = {self.visited}'
def __repr__(self):
return f'{self.name}'
def add_path(self, node_to):
if isinstance(node_to, Node):
if node_to not in self.neighbours:
self.neighbours.append(node_to)
else:
print(f'Error, added node_to is already a neighbour of {self.name}')
else:
print(f'Error adding the new Node neighbour, it must be a instance of Node')
def has_unvisited_neighbour(self):
"""Check the Node's neighbours, return False if even one node is False hence not visited"""
check_neighbours = [node.visited for node in self.neighbours]
return all(check_neighbours)
class Graph:
def __init__(self, nodes: list):
self.nodes = {node: Node(node) for node in nodes}
def create_graph(self, paths: list):
node_from, nodes_to = paths
if node_from in self.nodes:
get_node_from = self.nodes.get(node_from)
for node in nodes_to:
get_node_to = self.nodes.get(node)
self.nodes[node_from].add_path(get_node_to)
self.nodes[node].add_path(get_node_from)
else:
print('Error while creating Graph, an unknown node was entered :(')
def __repr__(self):
return f'Graph({self.nodes})'
def show_nodes(self):
for node in self.nodes.values():
print(node)
def dft_recursive(self, starting_vertex):
starting_vertex = self.nodes[starting_vertex]
starting_vertex.visited = True
for neighbor in starting_vertex.neighbours:
if not neighbor.visited:
neighbor.visited = True
neighbor.previous_node = starting_vertex # NOTE: This is just to show the printed result not really needed
if not neighbor.has_unvisited_neighbour(): # If False means we reached a dead end
print(starting_vertex.name, end=' --> ')
self.dft_recursive(neighbor.name)
else:
print(neighbor.previous_node.name, '--> ', neighbor.name, '| ')
continue
nodes_list = ['Earth', 'Moon', 'Mars', 'Venus',
'Mercury', 'Jupiter', 'Saturn',
'Neptune', 'Uranus', 'Sun', 'Comet', 'Blackhole']
path_earth = ['Earth', ('Moon', 'Mars', 'Venus')]
path_venus = ['Venus', ('Blackhole',)]
path_mercury = ['Mercury', ('Sun', 'Mars', 'Comet')]
path_mars = ['Mars', ('Jupiter', )]
path_jupiter = ['Jupiter', ('Saturn',)]
path_saturn = ['Saturn', ('Neptune',)]
path_neptune = ['Neptune', ('Uranus',)]
paths = [path_earth, path_venus, path_mercury, path_mars, path_jupiter, path_saturn, path_neptune]
# ----- Creating the Graph
my_graph = Graph(nodes_list)
for path in paths:
my_graph.create_graph(path)
my_graph.dft_recursive('Earth')
2。使用有状态闭包
Python 具有 first-class 函数，这意味着您可以将它们分配给变量，将它们作为
其他函数的参数，在表达式中比较它们等
A Closure 是一个函数对象，它会记住封闭作用域中的值，即使它们不存在于内存中，你可以看到它在 stateful_closure 函数中实现.
class Graph:
def __init__(self, nodes: list):
self.nodes = {node: [] for node in nodes}
def create_graph(self, paths: list):
node_from, nodes_to = paths
if node_from in self.nodes:
for node in nodes_to:
self.nodes[node_from].append(node)
self.nodes[node].append(node_from)
else:
print('Error while creating Graph, an unknown node was entered :(')
def dft_recursive(self, starting_vertex):
"""Depth First Search using a stateful closure to keep track of Visited Node"""
visited_nodes = set()
def stateful_closure(starting_vertex):
"""Recursive stateful Closure function"""
visited_nodes.add(starting_vertex) # FAQ: This is a Closure
starting_vertex_name = starting_vertex
starting_vertex = self.nodes[starting_vertex]
for neighbor in starting_vertex:
if neighbor not in visited_nodes:
visited_nodes.add(neighbor)
if not all([bool(node in visited_nodes) for node in self.nodes[neighbor]]):
print(starting_vertex_name, end=' --> ')
stateful_closure(neighbor)
else:
print(starting_vertex_name, '--> ', neighbor, '| ')
continue
stateful_closure(starting_vertex)
# Same as prev function, shorted form to save space
nodes_list = ['Earth', 'Moon', 'Mars', 'Venus',
'Mercury', 'Jupiter', 'Saturn',
'Neptune', 'Uranus', 'Sun', 'Comet', 'Blackhole']
paths = [['Earth', ('Moon', 'Mars', 'Venus')], ['Venus', ('Blackhole',)], ['Mercury', ('Sun', 'Mars', 'Comet')],
['Mars', ('Jupiter', )], ['Jupiter', ('Saturn',)], ['Saturn', ('Neptune',)], ['Neptune', ('Uranus',)]]
# ----- Creating the Graph
my_graph = Graph(nodes_list)
for path in paths:
my_graph.create_graph(path)
my_graph.dft_recursive('Earth')
文档 |指南 |其他 Whosebug 答案
- Can a Python function remember its previous outputs?
- Closures
有没有办法在不传递已访问节点的“已访问”参数集（或将一个作为 class 属性或全局变量）的情况下递归地进行基于图的深度优先遍历？
维基百科上的伪代码似乎表明这是必要的。
我的代码（如下）在我将默认参数添加到给我的签名后工作。我根本不想弄乱函数签名，因为它是在单元测试中调用的。然而，默认参数被证明既有用又有害，但如果我必须使用递归，这是我能做到的唯一方法吗？
def dft_recursive(self, starting_vertex, visited = set()):
"""
Print each vertex in depth-first order
beginning from starting_vertex.
This should be done using recursion.
"""
print(starting_vertex)
visited.add(starting_vertex)
for neighbor in self.vertices[starting_vertex]:
if neighbor not in visited:
visited.add(neighbor)
self.dft_recursive(neighbor, visited)
为了证明这一点，让我们考虑以下 undirected graphs 图：
1。使用节点 Class 实例
实现节点的 Class，它存储 Visited 布尔标志状态本身。
另请注意，将 neighbours 存储在节点的 Class 本身中。
class Node:
def __init__(self, name):
self.name = name
self.neighbours = []
self.visited = False
self.previous_node = None # NOTE: This is just to show the printed result not really needed
def __str__(self):
return f'{self.name} can go to = {self.neighbours}, is Visited? = {self.visited}'
def __repr__(self):
return f'{self.name}'
def add_path(self, node_to):
if isinstance(node_to, Node):
if node_to not in self.neighbours:
self.neighbours.append(node_to)
else:
print(f'Error, added node_to is already a neighbour of {self.name}')
else:
print(f'Error adding the new Node neighbour, it must be a instance of Node')
def has_unvisited_neighbour(self):
"""Check the Node's neighbours, return False if even one node is False hence not visited"""
check_neighbours = [node.visited for node in self.neighbours]
return all(check_neighbours)
class Graph:
def __init__(self, nodes: list):
self.nodes = {node: Node(node) for node in nodes}
def create_graph(self, paths: list):
node_from, nodes_to = paths
if node_from in self.nodes:
get_node_from = self.nodes.get(node_from)
for node in nodes_to:
get_node_to = self.nodes.get(node)
self.nodes[node_from].add_path(get_node_to)
self.nodes[node].add_path(get_node_from)
else:
print('Error while creating Graph, an unknown node was entered :(')
def __repr__(self):
return f'Graph({self.nodes})'
def show_nodes(self):
for node in self.nodes.values():
print(node)
def dft_recursive(self, starting_vertex):
starting_vertex = self.nodes[starting_vertex]
starting_vertex.visited = True
for neighbor in starting_vertex.neighbours:
if not neighbor.visited:
neighbor.visited = True
neighbor.previous_node = starting_vertex # NOTE: This is just to show the printed result not really needed
if not neighbor.has_unvisited_neighbour(): # If False means we reached a dead end
print(starting_vertex.name, end=' --> ')
self.dft_recursive(neighbor.name)
else:
print(neighbor.previous_node.name, '--> ', neighbor.name, '| ')
continue
nodes_list = ['Earth', 'Moon', 'Mars', 'Venus',
'Mercury', 'Jupiter', 'Saturn',
'Neptune', 'Uranus', 'Sun', 'Comet', 'Blackhole']
path_earth = ['Earth', ('Moon', 'Mars', 'Venus')]
path_venus = ['Venus', ('Blackhole',)]
path_mercury = ['Mercury', ('Sun', 'Mars', 'Comet')]
path_mars = ['Mars', ('Jupiter', )]
path_jupiter = ['Jupiter', ('Saturn',)]
path_saturn = ['Saturn', ('Neptune',)]
path_neptune = ['Neptune', ('Uranus',)]
paths = [path_earth, path_venus, path_mercury, path_mars, path_jupiter, path_saturn, path_neptune]
# ----- Creating the Graph
my_graph = Graph(nodes_list)
for path in paths:
my_graph.create_graph(path)
my_graph.dft_recursive('Earth')
2。使用有状态闭包
Python 具有 first-class 函数，这意味着您可以将它们分配给变量，将它们作为 其他函数的参数，在表达式中比较它们等
A Closure 是一个函数对象，它会记住封闭作用域中的值，即使它们不存在于内存中，你可以看到它在 stateful_closure 函数中实现.
class Graph:
def __init__(self, nodes: list):
self.nodes = {node: [] for node in nodes}
def create_graph(self, paths: list):
node_from, nodes_to = paths
if node_from in self.nodes:
for node in nodes_to:
self.nodes[node_from].append(node)
self.nodes[node].append(node_from)
else:
print('Error while creating Graph, an unknown node was entered :(')
def dft_recursive(self, starting_vertex):
"""Depth First Search using a stateful closure to keep track of Visited Node"""
visited_nodes = set()
def stateful_closure(starting_vertex):
"""Recursive stateful Closure function"""
visited_nodes.add(starting_vertex) # FAQ: This is a Closure
starting_vertex_name = starting_vertex
starting_vertex = self.nodes[starting_vertex]
for neighbor in starting_vertex:
if neighbor not in visited_nodes:
visited_nodes.add(neighbor)
if not all([bool(node in visited_nodes) for node in self.nodes[neighbor]]):
print(starting_vertex_name, end=' --> ')
stateful_closure(neighbor)
else:
print(starting_vertex_name, '--> ', neighbor, '| ')
continue
stateful_closure(starting_vertex)
# Same as prev function, shorted form to save space
nodes_list = ['Earth', 'Moon', 'Mars', 'Venus',
'Mercury', 'Jupiter', 'Saturn',
'Neptune', 'Uranus', 'Sun', 'Comet', 'Blackhole']
paths = [['Earth', ('Moon', 'Mars', 'Venus')], ['Venus', ('Blackhole',)], ['Mercury', ('Sun', 'Mars', 'Comet')],
['Mars', ('Jupiter', )], ['Jupiter', ('Saturn',)], ['Saturn', ('Neptune',)], ['Neptune', ('Uranus',)]]
# ----- Creating the Graph
my_graph = Graph(nodes_list)
for path in paths:
my_graph.create_graph(path)
my_graph.dft_recursive('Earth')
文档 |指南 |其他 Whosebug 答案
- Can a Python function remember its previous outputs?
- Closures