Search code examples
algorithmsortingdata-structuresnodestopological-sort

What to do in a topological sort if, after decreasing adjacent node values none are reduced to 0?

So my understanding of topological sort is as follows:

  • You assign each node an indegree, or number of incoming edges

  • You start with the node that has an indegree of 0 and enqueue it

  • Once it is queued, you look for adjacent nodes of the queued node and decrease their indegree by 1. If the indegree value of said nodes is 0, then you add it to the queue and repeat steps 2-3 until completion.

However, what if when you decrease the indegree values of the adjacent nodes and none of them resolve to 0? Below is a picture that illustrates my problem

Topological sort problem

Solution

  • The mistake is in step 1, where you did not decrease the indegree of node D. Then, after step 2, both H and D would be added to the queue. It is okay not to get any nodes to 0 indegree in a step, as long as you still have nodes in your queue to go on.