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

Поиск в ширину

Идея метода. Суть (в сжатой формулировке) заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины - выбирается та, которая была раньше рассмотрена. Для реализации данного принципа необходима структура данных “очередь”.

Пример. Исходный граф на левом рисунке. На правом рисунке рядом с вершинами в скобках указана очередность просмотра вершин графа.

Приведем процедуру реализации данного метода обхода вершин графа.

Логика просмотра вершин.

procedure PW(v:integer);

var Og:array[1..N] of 0..N; {очередь}

yk1,yk2:integer; {указатели очереди, yk1 - запись; yk2 - чтение}

j:integer;

begin

FillChar(Og,SizeOf(Og),0);yk1:=0;yk2:=0; {начальная инициализация}

Inc(yk1);Og[yk1]:=v;Nnew[v]:=false; {в очередь - вершину v}

while yk2<yk1 do begin {пока очередь не пуста}

Inc(yk2);v:=Og[yk2];write(v:3); {“берем” элемент из очереди}

for j:=1 to N do {просмотр всех вершин, связанных с вершиной v}

if (A[v,j]<>0) and Nnew[j] then begin {если вершина ранее не просмотрена}

Inc(yk1);Og[yk1]:=j;Nnew[j]:=false; {заносим ее в очередь}

end;

end;

end;

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

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

Дата добавления: 2014-01-11