Delphi World - Топологическая сортировка
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Топологическая сортировка

Нерекурсивный алгоритм топологической сортировки ориентированного графа без циклов.

Предположим, что граф имеет вершины с номерами 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] - но и это не беспредельно.

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования