algorithme pour traveral BFS d'un graphe orienté de acylic

Question

Je suis à la recherche d'un programme Python élégant qui fait un traveral BFS d'un DAG:

nœud A est connecté à B (A->B) si A "dépend de" B (pensez au paquet python Foo "en fonction de" Bar: Foo-> Bar).

Dans un graphique d'environ 7000 tels noeuds, je veux trier tous les noeuds de sorte que pour tous possible (i, j) où 1>=i<j<=7000 .. depends(Ni, Nj) est faux. depends (A, B) = True si et seulement si A->B ou A "dépend de" B .. et Nx est le nœud se trouvant en x ème position dans la liste triée.

Remarque: Un noeud peut avoir plusieurs parents. Ex: A-> C et B-> C. Par conséquent, selon la règle de tri ci-dessus, A et B doivent venir avant C.

Answer 1

Si je lis la question correctement, il semble que vous voulez un topological sort. L'algorithme le plus efficace (O (V + E)) pour ce faire a été proposé par Tarjan, et une implémentation Python peut être trouvée here.

Hors sujet, mais il semble que votre analogie de dépendance de paquet soit inversée; Je penserais que "A dépend de B" impliquerait "B-> A", mais bien sûr cela ne changera pas la structure de l'arbre, il suffit de l'inverser.