如何查找拓扑排序的所有结果

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)