Поскольку существующая нерекурсивная реализация 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, и чисто локальный алгоритм поиска не может заранее сказать, найдет ли он такое ребро или нет. Таким образом, в некотором смысле плохая выходная чувствительность таких наивных поисков обусловлена недостаточной осведомленностью о глобальной структуре графика.
Хотя существуют различные методы предварительной обработки (такие как итеративное удаление конечных узлов, поиск одноузловых разделителей вершин и т. Д.), Которые можно использовать, чтобы избежать некоторых из этих «тупиковых показателей экспоненциального времени», я не знаю любой уловки предварительной обработки, которая могла бы устранить их в всех случаях. Общее решение состоит в том, чтобы на каждом этапе поиска проверять, достижим ли целевой узел (используя дополнительный поиск), и быстро возвращаться назад, если это не & mdash; но увы, это значительно замедлило бы поиск (в худшем случае, пропорционально размеру графика) для многих графиков, которые не содержат такие патологические тупики.