CODEWITHSUNDEEP
algorithmgraphcomputer-sciencetopological-sort
Elad Benda
Elad Benda

Reputation: 36656

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

Upvotes: 4

Views: 1653

Answers (2)

phant0m
phant0m

Reputation: 16905

  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

Upvotes: 3

Srikant Krishna
Srikant Krishna

Reputation: 881

You will have to decompose the graph into an adjacency matrix, in which every link from Node A to Node B is represented as a "1" in a matrix in which nodes correspond to nodes and columns.

From this point, all you need to do is work backwards from a terminal node, identify the nodes that are pointing to it, and then work backwards from each of those as well.

Now, you would probably want to do this in a breadth-first way, so use a queue data structure to keep track of "dependent" nodes.

Upvotes: 1

Related Questions