HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Sort an array based on dependencies

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
arraysortdependenciesbased

Problem

I have an array of objects, each of them has a numeric id and another array attached to them.

The array in the object contains the dependencies of that object. Each dependency is an id from the other objects. There are no circular dependencies.

Let's take this diagram:

The ids of the objects are in the upper rectangle, the dependecies are in the lower one.

I need to sort the array in a way, so if an object depends on another object, then it needs to be after that object in the array.

So for the example above it would be

3 1 2 4

Solution

You effectively have a directed graph here, where your vertices are the entries of your array, and you have an edge $(i,j)$ between entries $i$ and $j$ iff $j$ depends on $i$. What you want is a topological sort of this graph (https://en.wikipedia.org/wiki/Topological_sorting).

Context

StackExchange Computer Science Q#60136, answer score: 4

Revisions (0)

No revisions yet.