Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Сортировка /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Топологическая сортировка - Программирование от RIN.RU
Топологическая сортировка

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


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



 8  Комментарии к статье  8  Обсудить в форуме  8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь