CODEWITHSUNDEEP
algorithmsorting
Androme
Androme

Reputation: 2449

Sorting algorithms with requirements

I am looking for an algorithm that can do sorting with requirements. As an example if I have 3 nodes N1, N2 and N3 I have the requirement that N2 must come after N3, and N3 have the requirement that it must come after N1. So the correct sort will be N1, N3, N2.

Upvotes: 0

Views: 56

Answers (1)

Timothy Shields
Timothy Shields

Reputation: 79461

Form a graph from your requirements. Your items are the nodes and there is a directed edge from A to B if A must come before B. Repeatedly, remove a node that has no incoming edges and remove all of its outgoing edges. Do this until you have removed all the nodes. You will have removed them in the desired order, satisfying the requirements.

For the details of the implementation, see here: Topological sorting.

Upvotes: 5

Related Questions