Алгоритм топологической сортировки

Для упорядоченной пары элементов (a, b), элемент a будем называть предшественником, а элемент b преемником. Суть алгоритма заключается в следующем.

а) Для каждого элемента определяем его преемников и подсчитываем количество его предшественников. В дальнейшем работаем не с множеством элементов, каждому из которых приписан счетчик предшественников и список преемников.

б) Выбираем из построенного множества и помещаем в выходной список элементы, не имеющие предшественников (с нулевым счетчиком).

в) Каждое извлечение элемента (см. пункт б) сопровождаем пересчетом количества оставшихся предшественников. Причем, эта операция затрагивает только те элементы, которые являются преемниками удаляемого.

Пункты б) и в) повторяем до тех пор, пока это возможно. Если в очередной раз пункт б) не выполним, а множество непустое, то топологическая сортировка невозможна. Если же множество исчерпано, то топологическая сортировка выполнена "удачно" и в выходном списке перечислены элементы в допустимом порядке.