Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Topological sort to find dependencies of a specific node

Given the following graph:

enter image description here

What algorithm can I use to output topological ordered lists with tasks to complete, and that are relevant for just for a specific node?

For example, considering the node 2, the list should be:

7, 5, 11, 2

or

5, 7, 11, 2
like image 931
Elad Benda Avatar asked Oct 31 '25 17:10

Elad Benda


1 Answers

  1. Reverse the edges
  2. Run a DFS starting from 2
  3. Upon leaving a node, insert it into the list.

Example:

Enter 2
  Enter 11
    Enter 7
    Leave 7, insert into list
    Enter 5
    Leave 5, insert into list
  Leave 11, insert into list
Done, insert 2 into list

Result: 7, 5, 11, 2
like image 144
phant0m Avatar answered Nov 03 '25 13:11

phant0m



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!