Question

Ok, my situation is this I have a list of items and I need to get the order of these items based on the references they have. For example lets say we have these items: A,B,C,D,E,F

C and D have no dependencies so their order can be 0. B is the one that has the most with C, D and A. A has C and F has A and B

  C    D    
  |   /
  A  /
/ | /
| B 
 |
  F

In this case C,D = 0 A = 1 B= 2 F = 3

I have been looking through the internet and it seems I am not using the correct scientific term for this. Most probably it is a Set or a Bag set in some way. I know it is not a tree as this situation has more than two edges on each node. The answer can be in a programming language, just trying to make it as general as possible.

Answer 1

A simple algorithm is as follows.

Iterate the collection, looking for elements which have no dependencies: remember these elements as "the level 0 elements".

Iterate the collection again, looking for elements which may depend on "the level 0 elements" but not on other elements: remember these elements as "the level 1 elements".

Iterate the collection again, looking for elements which may depend on "the level 0 elements" and/or on "the level 1 elements", but not on other elements: remember these elements as "the level 2 elements".

Etc.

Stop when every element has an assigned level.

Answer 2

You can create a graph and maintain the pointer counts, or you can use matrix. Search and read some basic idea of graph(math, not computer graph), you can find it is pretty easy.

友情链接