How to find all results of topological sorting
-
09-04-2021 - |
Question
Since the results in topological sorting are not unique, there are other reasonable results. I have some relations like a->b b->c... etc. These relations are parts of a graph. I need to find all lists between root and destination(just one destination). Let root n, and destination i.
n-a-b-i
n-a-d-i
n-c-b-i
n-c-d-i
I thought i can reach these results using topological sorting but how? Thanks in advance.
Solution
You shouldn't need topological sorting. Just use either breadth-first search or depth-first search from the root and store all paths that end at the destination.
Example pseudocode 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)
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow