Почему L1 появляется дважды в вашем списке?Потому что у вас есть два пути, которые ведут к L4A: L1 -> L2 -> L3A -> L4A и L1 -> L4A, но только одна переменная path для хранения этих путей.Поскольку вы используете вид обратного DFS , у вас есть уровни: L4 -> L3A -> L2 -> L1, затем L4 -> L1.
Давайте попробуем разработать алгоритм.Вы имеете дело с графиком (если вы добавляете корень, вы получаете дерево), поэтому я буду использовать обычный словарь: уровни - это «узлы», а пути между уровнями - это «ребра».Вот хороший способ продолжить:
- дано: узел
N - найти все узлы
P так, чтобы ребро P-N существовало и сохранить пути. - для каждого
P найдите все узлы Q, так что ребро P-Q существует, и сохраните пути. - , как только не останется
edge к узлу Q, то есть текущий path максимален, возвращает path.
Ему не хватает точности, чтобы быть реальным алгоритмом.Давайте сосредоточимся:
GIVEN: a node N
let paths_to_explore = [N]
while paths_to_explore is not empty:
for every path_to_explore:
try to add a node at the beginning of path_to_explore
if it fails, yield path_to_explore
Прежде чем я перейду к коду, обратите внимание, что ваше представление графа не является одним из двух обычных представлений.В вашем случае у вас есть список ребер, но словарь from_node -> [to_nodes] лучше:
edges = {
"L3A": {"L4A"},
"L3B": {"L4B"},
"L3C": {"L4C"},
"L1": {"L2", "L4A"},
"L2": {"L3A", "L3B", "L3C"},
}
Это облегчает итерацию по ребрам:
for from_node, to_nodes in edges.items():
# do something with nodes
Теперь код:
def find_reverse_path(name):
paths = []
paths_to_explore = [[name]]
while paths_to_explore:
path = paths_to_explore.pop() # next!
to_node = path[0] # the HEAD of the current path
expanded = False
for from_node, to_nodes in edges.items():
if to_node in to_nodes: # there's an edge to the HEAD
new_path_to_explore = [from_node] + path # new path = from_node + old path
paths_to_explore.append(new_path_to_explore) # add it to the exploration list
expanded = True # this path was expanded
if not expanded: # the path is maximal
paths.append(path) # use yield if you want to create a generator
return paths
print(find_reverse_path("L4A"))
Вывод:
[['L1', 'L4A'], ['L1', 'L2', 'L3A', 'L4A']]
Это итеративная DFS.(Думаю, нам было бы сложнее узнать, был ли путь расширен в рекурсивной DFS.)
Посмотрите на эти две строки, они содержат "трюк":
new_path_to_explore = [from_node] + path # new path = from_node - old path
paths_to_explore.append(new_path_to_explore) # add it to the exploration list
Примечаниечто new_path_to_explore является копией из path, это означает, что мы не просто добавляем узел к paths[-1] (на месте).Это почему?Посмотрите на первые шаги:
1. paths = [[L4A]]
2. paths = [], path = [L4A]
3. append L1-L4A to paths, then append L3A-L4A to paths
4. paths = [[L1, L4A], [L3A, L4A]]
5. paths = [[L1, L4A]], path = [L3A, L4A]
...
Если мы не сделаем копию и если мы найдем несколько ребер в начале текущего пути, мы получим шаг 4 paths = [[L3A, L1, L4]].Это было бы почти той же проблемой, что и у вас в коде.