Топологическая сортировка
Материал из DRKB
Нерекурсивный алгоритм топологической сортировки ориентированного графа без циклов.
Предположим, что граф имеет вершины с номерами 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, напечатаны }
Доказательство, что если в графе нет циклов, то этот алгоритм заканчивает работу:
Пусть это не так. Каждая вершина может печататься только один раз, так что с некоторого момента вершины не печатаются. В графе без циклов длина пути ограничена (вершина не может входить дважды), поэтому подождав еще, мы можем дождаться момента, после которого путь не удлиняется. После этого может разве что увеличиваться edge[l] - но и это не беспредельно.
Source: http://algolist.manual.ru
ID: 04157