Изменения
→Реализация
===Реализация===
<wikitex>Пусть граф задан матрицей смежности $A = (a_{ij})$, где $a_{ij} = 1$ тогда, и только тогда, когда существует ребро $i \to j$. За $N(i)$ обозначим число детей вершины $i$, а $schedule$ - расписание.
'''for ''' i = 1 '''to ''' n do '''for ''' j = 1 '''to ''' n do N[i] += A[i][j]; S = {1,...,n}; P = sum(p[i]); '''for ''' k = n '''downto ''' 1 do find job j in S with N[j] == 0 and minimal f[j](P)-value; S = S \ {j}; N[i] = inf;<tex>\infty</tex> schedule[k] = j; P -= p[j]; '''for ''' i = 1 '''to ''' n do '''if ''' A[i][j] == 1 then N[i]--;
Сложность этого алгоритма $O(n^2)$.
