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

Question

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

н-а-б-я

н-а-д-я

н-с-б-я

н-с-д-я

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

Answer 1

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

Пример псевдокода ДФС:

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)