Sorting Hierarchically a Set of Items based on their requirements-CodePudding

I have a collection of instructions which work like this:

Item A: Requires B, C
Item B: Requires C, D
Item C: Requires Nothing
Item D: Requires C

The sorted list of instructions should have A as the last one as it is the one requiring the most items and C as the first one as it requires nothing. Moreover, in this case the order would be unique as D would need to happen for B to be created, meaning that the definitive order would be this:

I tried looking online for similar algorithm but I could not find any, although maybe this problem has a particular name I am not aware of and this could be why I could not find any solution.

So, is there an algorithm for solving this kind of problem?

CodePudding user response：

this looks like a topological sorting problem which can be solved using directed acyclic graphs (DAGs). There are a lot of resources on topological sorting online - here are a useful few:

https://www.geeksforgeeks.org/topological-sorting/

https://en.wikipedia.org/wiki/Topological_sorting

CodePudding user response：

Im not aware of any particuar algorithm for this, but off the top of my head, one approach to this would be to try and calculate a weight/priority of each item.

We can start by giving each item a priority of 1, then looping over all the item's dependencies and adding that item's priority onto our priority.

e.g.

Item A = 1   B   C ( 1   2   1) = (4)
Item B = 1   C   D (1   1   1) = (3)
Item C = 1   Nothing (1   0) = (1)
Item D = 1   C (1   1) = (2)

Which would then give them the order of C -> D -> B -> A