3622
правки
Изменения
м
→Алгоритм
Детали описаны в алгоритме ниже, в котором
* <tex> E(i) </tex> обозначает последнюю работу в последовательности <tex> \pi_i </tex>,
* <tex> P(i) </tex> обозначает предка в графе зависимостей, а после слияния с какой-то вершиной <tex> j </tex> {{---}} предыдущую работу в последовательности <tex> \pi_j </tex>.
После завершения этой процедуры оптимальное расписание можно восстановить с конца, зная <tex> E(root) </tex> и массив <tex> P </tex>.
Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> \mathcal{O}(n\log{n}) </tex>.
Проиллюстрируем работу алгоритма на следующем примере.
