c++ - 如何找到拓扑排序的所有结果

Question

由于拓扑排序的结果不是唯一的，所以还有其他合理的结果。我有一些关系，例如 a->b b->c... 等。这些关系是图形的一部分。我需要找到根和目的地之间的所有列表(只有一个目的地)。令根为 n，目的地为 i。

n-a-b-i

n-a-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)