Топологическая сортировка на графе без рекурсии

Задача. Составить нерекурсивный алгоритм топологической сортировки ориентированного графа без циклов. Решение. Предположим, что граф имеет вершины с номерами 1..n, для каждой вершины i известно число num[i] выходящих из нее ребер и номера вершин dest[i][1],..., dest[i][num[i]], в которые эти ребра ведут. Будем условно считать, что ребра перечислены "слева направо": левее то ребро, у которого номер меньше.

Нам надо напечатать все вершины в таком порядке, чтобы конец любого ребра был напечатан перед его началом. Мы предполагаем, что в графе нет ориентированных циклов - иначе такое невозможно. Для начала добавим к графу вершину 0, из которой ребра ведут в вершины 1,...,n. Если ее удастся напечатать с соблюдением правил, то тем самым все вершины будут напечатаны.

Алгоритм хранит путь, выходящий из нулевой вершины и идущий по ребрам графа. Переменная l отводится для длины этого пути. Путь образован вершинами vert[1],..., vert[l] и ребрами, имеющими номера edge[1]...edge[l]. Номер edge[s] относится к нумерации ребер, выходящих из вершины vert[s]. Тем самым для всехs должны выполняться неравенство

edge[s] < = num[vert[s]]

и равенство

vert[s+1] = dest [vert[s]] [edge[s]]

Впрочем, для последнего ребра мы сделаем исключение, разрешив ему указывать "в пустоту", т.е. разрешим edge[l] равняться num[vert[l]]+1.

В процессе работы алгоритм будет печатать номера вершин, при этом соблюдая требование "вершина напечатана только после тех вершин, в которые из нее ведут ребра". Наконец, будет выпол- няться такое требование: вершины пути, кроме последней (т.е. vert[1]..vert[l]) не напечатаны, но свернув с пути налево, мы немедленно упираемся в напечатанную вершину.

Вот что получается:

l:=1; vert[1]:=0; edge[1]:=1;
 while not( (l=1) and (edge[1]=n+1)) do begin
 | if edge[l]=num[vert[l]]+1 then begin
 | | {путь кончается в пустоте, поэтому все вершины,
 | | следующие за vert[l], напечатаны - можно
 | | печатать vert[l]}
 | | writeln (vert[l]);
 | | l:=l-1; edge[l]:=egde[l]+1;
 | end else begin
 | | {edge[l] <= num[vert[l]], путь кончается в
 | | вершине}
 | | lastvert:= dest[vert[l]][edge[l]]; {последняя}
 | | if lastvert напечатана then begin
 | | | edge[l]:=edge[l]+1;
 | | end else begin
 | | | l:=l+1; vert[l]:=lastvert; edge[l]:=1;
 | | end;
 | end;
 end;
 {путь сразу же ведет в пустоту, поэтому все вершины
 левее, то есть 1..n, напечатаны}