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

Формулировка

Основная идея алгоритма Демукрона состоит в последовательном удалении из графа, начиная со входов, вершин и исходящих из них дуг .

Примечания

Литература

• Белоусов А. И., Ткачев С. Б. Дискретная математика. — М. : МГТУ, 2006. — 744 с. — ISBN 5-7038-2886-4 .