トポロジカルソートのすべての結果を見つける方法

Question

トポロジカルソートの結果は一意ではないので、他の合理的な結果があります。私はa-> bb-> c ...のような関係を持っています。これらの関係はグラフの一部です。ルートとデスティネーションの間ですべてのリストを見つける必要があります（ただ1つのデスティネーション）。ルートn、宛先iとする。

のn--B-I

のn--D-I

N-C-B-I

のn-C-D-I

私は私がトポロジカル整列が、どのように使用して、これらの結果に達することができると思いましたか？前もって感謝します。

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)