Question

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
Was it helpful?

Solution

  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

OTHER TIPS

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top