Алгоритм BFS-путешествия ациклического ориентированного графа

Question

Я ищу элегантную программу на Python, которая выполняет BFS для DAG:

Узел A подключен к B (A->B), если A "зависит от" B (подумайте о пакете Python Foo "в зависимости от" Bar: Foo-> Bar).

На графике из примерно 7000 таких узлов я хочу отсортировать все узлы таким образом, чтобы для всех возможных (i, j), где 1>=i<j<=7000 .. depends(Ni, Nj) - False. зависимость (A, B) = True тогда и только тогда, когда A->B или A "зависит от" B .. и Nx - это узел, находящийся на x-й позиции в отсортированном списке.

Примечание. У узла может быть несколько родителей. Например: A-> C и B-> C. Следовательно, согласно приведенному выше правилу сортировки, A и B должны предшествовать C.

Answer 1

Если я правильно читаю вопрос, похоже, вы хотите топологическая сортировка . Наиболее эффективный алгоритм (O (V + E)) для этого был предложен Tarjan , и реализацию Python можно найти здесь .

Не по теме, но похоже, что аналогия с зависимостями вашего пакета обратная; Я думаю, что «A зависит от B» будет означать «B-> A», но, конечно, это не изменит структуру дерева, а только изменит его.