Как найти все результаты топологической сортировки

Question

Поскольку результаты топологической сортировки не являются уникальными, существуют и другие разумные результаты. У меня есть некоторые отношения, такие как a-> b b-> c ... и т.д. Эти отношения являются частями графа. Мне нужно найти все списки между корнем и пунктом назначения (только один пункт назначения). Пусть корень п, а пункт назначения я.

п-а-б-я

п-а-д-я

п-с-б-я

N-C-D-я

Я думал, что смогу достичь этих результатов, используя топологическую сортировку, но как? Заранее спасибо.

Answer 1

Вам не нужна топологическая сортировка. Просто используйте поиск в ширину или поиск в глубину из корня и сохраните все пути, которые заканчиваются в месте назначения.

Пример псевдокода DFS:

paths_to_destination = []

def dfs_store_destination(node, dest, path=None):
    if path is None:
         path = []

    Append node to path

    if node == dest:
        Add path to paths_to_destination
    else:
        for new_node in node.reachable_nodes:
            dfs_store_destination(new_node, dest, path)

    Remove node from path

dfs_store_destination(root, my_dest)