Ответ 1
Нелегко включить итеративную реализацию DFS в топологическую сортировку, поскольку изменение, которое нужно сделать, более естественно с рекурсивной реализацией. Но вы все равно можете это сделать, просто требуется, чтобы вы реализовали свой собственный стек.
Прежде всего, здесь немного улучшена версия вашего кода (это намного эффективнее и не намного сложнее):
def iterative_dfs_improved(graph, start):
seen = set() # efficient set to look up nodes in
path = [] # there was no good reason for this to be an argument in your code
q = [start]
while q:
v = q.pop() # no reason not to pop from the end, where it fast
if v not in seen:
seen.add(v)
path.append(v)
q.extend(graph[v]) # this will add the nodes in a slightly different order
# if you want the same order, use reversed(graph[v])
return path
Вот как я могу изменить этот код, чтобы сделать топологическую сортировку:
def iterative_topological_sort(graph, start):
seen = set()
stack = [] # path variable is gone, stack and order are new
order = [] # order will be in reverse order at first
q = [start]
while q:
v = q.pop()
if v not in seen:
seen.add(v) # no need to append to path any more
q.extend(graph[v])
while stack and v not in graph[stack[-1]]: # new stuff here!
order.append(stack.pop())
stack.append(v)
return stack + order[::-1] # new return value!
Часть, которую я прокомментировал с помощью "нового материала здесь", - это часть, которая определяет порядок при перемещении вверх по стеку. Он проверяет, был ли найден новый node дочерний элемент предыдущего node (который находится в верхней части стека). Если нет, то всплывает верхняя часть стека и добавляется значение order. Пока мы делаем DFS, order будет в обратном топологическом порядке, начиная с последних значений. Мы отменяем его в конце функции и объединяем его с остальными значениями в стеке (которые удобно уже в правильном порядке).
Поскольку этот код необходимо проверять v not in graph[stack[-1]] несколько раз, он будет намного эффективнее, если значения в словаре graph являются наборами, а не списками. Обычно граф не заботится о том, чтобы его ребра были сохранены, поэтому такое изменение не должно вызывать проблем с большинством других алгоритмов, хотя код, который создает или обновляет график, может потребовать исправления. Если вы когда-либо намереваетесь расширить свой графический код для поддержки взвешенных графиков, вы, вероятно, в конечном итоге измените списки на сопоставление словарей от node до веса, и это будет работать так же хорошо для этого кода (поиск в словарях O(1) точно так же, как набор запросов). В качестве альтернативы мы могли бы построить нужные нам наборы, если graph нельзя изменить напрямую.
Для справки, здесь рекурсивная версия DFS и ее модификация для топологической сортировки. Необходимая модификация очень мала:
def recursive_dfs(graph, node):
result = []
seen = set()
def recursive_helper(node):
for neighbor in graph[node]:
if neighbor not in seen:
result.append(neighbor) # this line will be replaced below
seen.add(neighbor)
recursive_helper(neighbor)
recursive_helper(node)
return result
def recursive_topological_sort(graph, node):
result = []
seen = set()
def recursive_helper(node):
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
recursive_helper(neighbor)
result.insert(0, node) # this line replaces the result.append line
recursive_helper(node)
return result
Что это! Одна строка удаляется, а аналогичная добавляется в другом месте. Если вам небезразлична производительность, вероятно, вы также должны сделать result.append во второй вспомогательной функции и сделать return result[::-1] в функции верхнего уровня recursive_topological_sort. Но использование insert(0, ...) является более минимальным изменением.
Также стоит отметить, что если вам нужен топологический порядок всего графика, вам не нужно указывать начальный node. В самом деле, не может быть ни одного node, который позволяет вам перемещаться по всему графику, поэтому вам может понадобиться сделать несколько обходов, чтобы добраться до всего. Простым способом сделать это в итеративной топологической сортировке является инициализация q до list(graph) (список всех графических клавиш) вместо списка только с одним стартовым node. Для рекурсивной версии замените вызов на recursive_helper(node) на цикл, который вызывает вспомогательную функцию на каждом node в графе, если он еще не находится в seen.