クラス属性または渡されたパラメーターなしで再帰的トラバーサルで訪問されたノードの再訪問/追跡を回避する方法はありますか？
gcr
訪問したノードの「訪問した」パラメータセットを渡すことなく（またはクラス属性またはグローバル変数として1つ持つことなく）、グラフベースの深さ優先探索を再帰的に実行する方法はありますか？
ウィキペディアの擬似コードは、それが必要であることを示しているようです。
私のコード（以下）は、与えられた署名にデフォルトのパラメーターを追加した後に機能します。単体テスト内で呼び出されているため、関数のシグネチャをいじりたくありませんでした。ただし、デフォルトのパラメーターは有用であり、害を及ぼすことが判明しましたが、再帰を使用する必要があると仮定すると、これが唯一の方法でしたか？
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)
フェデリコ・バウ
これを示すために、次の無向グラフグラフについて考えてみましょう。
1.ノードクラスインスタンスの使用
Visited booleanFlagステータス自体を格納するノードのクラスを実装します。またneighbours、ノードのクラス自体の中にを格納することにも注意してください。
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にはファーストクラスの関数があります。つまり、変数に割り当てたり、他の関数に引数として渡したり、式で比較したりできます。
A閉鎖は、彼らがメモリ内に存在しない場合でも、スコープを囲んで値を覚えて関数オブジェクトである、あなたはそれを実装すること見ることができる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')
ドキュメント| ガイド| その他のStackOverflowの回答
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
編集
コメントを追加