如何查找拓撲排序的所有結果

Question

由於拓撲排序的結果不是唯一的，還有其他合理的結果。我有一些關係，如a-> b b-> c ...等。這些關係是圖的一部分。我需要找到根目錄和目的地之間的所有列表（只有一個目的地）。讓根n和目的地i。

N-A-B-我

N-A-d-I

N-C-B-我

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)