Pseudocode pour obtenir l'ordre basé sur la dépendance

Question

Ok, ma situation est ceci j'ai une liste d'articles et je dois obtenir l'ordre de ces articles basés sur les références qu'ils ont. Par exemple, nous disons que avons ces articles: A, B, C, D, E, F

C et D ont aucune dépendance si leur ordre peut être 0. B est celui qui a le plus avec C, D et A. A a C et F a A et B

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

Dans ce cas C, D = 0 A = 1 B = 2 F = 3

je suis regardant à travers Internet et il semble que je n'utilise pas le terme scientifique correct pour cela. Très probablement, il s'agit d'un Set ou d'un Bag set d'une manière ou d'une autre. Je sais que ce n'est pas un arbre car cette situation a plus de deux arêtes sur chaque nœud. La réponse peut être dans un langage de programmation, essayant juste de le rendre aussi général que possible.

Answer 1

Un algorithme simple est le suivant. Iterate la collection, en recherchant les éléments qui n'ont pas de dépendances: rappelez-vous ces éléments comme "les éléments de niveau 0". Iterate la collection à nouveau, en recherchant les éléments qui peuvent dépendre des "éléments de niveau 0" mais pas sur d'autres éléments: souvenez-vous de ces éléments comme "les éléments de niveau 1". Itérer à nouveau la collection en recherchant les éléments qui peuvent dépendre des "éléments de niveau 0" et/ou des "éléments de niveau 1", mais pas des autres éléments: se souvenir de ces éléments comme "les éléments de niveau 2".

Etc

Arrêtez lorsque chaque élément a un niveau attribué.

Answer 2

Vous pouvez créer un graphique et gérer le nombre de pointeurs, ou vous pouvez utiliser la matrice. Rechercher et lire une idée de base de graphique (maths, pas de graphique d'ordinateur), vous pouvez trouver c'est assez facile.