Кодинг
★ Рубрика: Кодинг
★ Тема: Алгоритмы

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

Задача. Пусть ориентированный граф без циклов хранится в такой форме: для каждого i от 1 до n в num[i] хранится число выходящих из i стрелок, в adr[i][1],..., adr[i][num[i]]- номера вершин, куда эти стрелки ведут. Составить (рекурсивный) алгоритм, который производит топологическую сортировку не более чем за C*(n+m) действий, где m - число ребер графа (стрелок).
Решение. Наша программа будет печатать номера вершин. В массиве printed: array[1..n] of boolean мы будем хранить сведения о том, какие вершины напечатаны (и корректировать их одновременно с печатью вершины). Будем говорить, что напечатанная последовательность вершин корректна, если никакая вершина не напечатана дважды и для любого номера i, входящего в эту последостельность, все вершины, в которые ведут стрелки из i, напечатаны, и притом до i.
procedure add (i: 1..n);
 | {дано: напечатанное корректно;}
 | {надо: напечатанное корректно и включает вершину i}
 begin
 | if printed [i] then begin {вершина i уже напечатана}
 | | {ничего делать не надо}
 | end else begin
 | | {напечатанное корректно}
 | | for j:=1 to num[i] do begin
 | | | add(adr[i][j]);
 | | end;
 | | {напечатанное корректно, все вершины, в которые из
 | | i ведут стрелки, уже напечатаны - так что можно
 | | печатать i, не нарушая корректности}
 | | if not printed[i] then begin
 | | | writeln(i); printed [i]:= TRUE;
 | | end;
 | end;
 end;
Основная программа:
for i:=1 to n do begin
 | printed[i]:= FALSE;
 end;
 for i:=1 to n do begin
 | add(i)
 end;
 Похожие публикации: Алгоритмы

Войдите, чтобы добавить Ваш ответ. [ Регистрация | Вход ]