Поскольку существующая нерекурсивная реализация DFS, указанная в этот ответ кажется неверным, позвольте предложить тот, который действительно работает.
Я написал это на Python, потому что считаю его довольно читаемым и не загроможденным деталями реализации (и потому что в нем есть удобное ключевое слово yield для реализации генераторы), но его будет довольно легко перенести на другие языки.
# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
visited = set()
visited.add(start)
nodestack = list()
indexstack = list()
current = start
i = 0
while True:
# get a list of the neighbors of the current node
neighbors = graph[current]
# find the next unvisited neighbor of this node, if any
while i < len(neighbors) and neighbors[i] in visited: i += 1
if i >= len(neighbors):
# we've reached the last neighbor of this node, backtrack
visited.remove(current)
if len(nodestack) < 1: break # can't backtrack, stop!
current = nodestack.pop()
i = indexstack.pop()
elif neighbors[i] == end:
# yay, we found the target node! let the caller process the path
yield nodestack + [current, end]
i += 1
else:
# push current node and index onto stacks, switch to neighbor
nodestack.append(current)
indexstack.append(i+1)
visited.add(neighbors[i])
current = neighbors[i]
i = 0
Этот код поддерживает два параллельных стека: один содержит более ранние узлы в текущем пути, а другой содержит индекс текущего соседа для каждого узла в стеке узлов (так что мы можем возобновить итерацию по соседям узла, когда мы вытолкнем его обратно. стек). Я мог бы с таким же успехом использовать один стек пар (узел, индекс), но я полагал, что метод с двумя стеками будет более читабельным и, возможно, более легким в реализации для пользователей других языков.
Этот код также использует отдельный набор visited, который всегда содержит текущий узел и любые узлы в стеке, чтобы я мог эффективно проверять, является ли узел уже частью текущего пути. Если ваш язык имеет структуру данных «упорядоченный набор», которая обеспечивает как эффективные, подобные стеку, операции push / pop и эффективные запросы членства, вы можете использовать это для стека узлов и избавиться от отдельных visited набор.
В качестве альтернативы, если вы используете настраиваемый изменяемый класс / структуру для своих узлов, вы можете просто сохранить логический флаг в каждом узле, чтобы указать, был ли он посещен как часть текущего пути поиска. Конечно, этот метод не позволит вам запустить два поиска на одном и том же графике параллельно, если вы по какой-то причине захотите это сделать.
Вот тестовый код, демонстрирующий, как работает приведенная выше функция:
# test graph:
# ,---B---.
# A | D
# `---C---'
graph = {
"A": ("B", "C"),
"B": ("A", "C", "D"),
"C": ("A", "B", "D"),
"D": ("B", "C"),
}
# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)
Запуск этого кода на приведенном примере графа дает следующий результат:
A -> B -> C -> D
A -> B -> D
A -> C -> B -> D
A -> C -> D
Обратите внимание, что хотя этот пример графа неориентированный (т.е. все его ребра идут в обе стороны), алгоритм также работает для произвольных ориентированных графов. Например, удаление края C -> B (путем удаления B из списка соседей C) дает тот же результат, за исключением третьего пути (A -> C -> B -> D), который больше невозможен.
Ps. Легко построить графики, для которых простые алгоритмы поиска, подобные этому (и другим, приведенным в этой теме), работают очень плохо.
Например, рассмотрим задачу поиска всех путей от A до B на неориентированном графе, где у начального узла A есть два соседа: целевой узел B (у которого нет других соседей, кроме A) и узел C, который является частью клика из n +1 узлов, например:
graph = {
"A": ("B", "C"),
"B": ("A"),
"C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
"H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
"I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
"J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
"K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
"L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
"M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
"N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
"O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}
Легко видеть, что единственный путь между A и B является прямым, но наивная DFS, запущенная с узла A, будет тратить O (n!) Времени на бесполезное исследование путей внутри клики, даже если это очевидно (для человека), что ни один из этих путей не может привести к B.
Также можно создавать DAG с аналогичными свойствами, например имея начальный узел A, соединяющий целевой узел B и два других узла C 1 и C 2, оба из которых подключаются к узлам D 1 и D 2, оба из которых подключаются к E 1 и E 2 и так далее. Для n слоев узлов, расположенных таким образом, наивный поиск всех путей от A до B приведет к потере O (2 n) времени. прежде чем сдаться, изучите все возможные тупики.
Конечно, добавление ребра к целевому узлу B из одного из узлов в клике (кроме C) или из последнего уровня DAG создаст экспоненциально большое количество возможных путей. от A до B, и алгоритм чисто локального поиска не может заранее сказать, найдет он такое ребро или нет. Таким образом, в некотором смысле низкая чувствительность вывода таких наивных поисков незнание глобальной структуры графа.
Хотя существуют различные методы предварительной обработки (такие как итеративное удаление листовых узлов, поиск одноузловых разделителей вершин и т. Д.), Которые можно использовать, чтобы избежать некоторых из этих «тупиков экспоненциального времени», я не знаю ни одного общего трюк с предварительной обработкой, который может устранить их во всех случаях. Общим решением было бы проверять на каждом этапе поиска, доступен ли целевой узел (с помощью подпоиска), и рано возвращаться, если это не так, но, увы, это значительно замедлит поиск (в худшем случае, пропорционально размеру графика) для многих графиков, не содержащих такие патологические тупики.
person
Ilmari Karonen
schedule
21.02.2016
