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

Топологическая сортировка (ТС) вершин орграфа G заключается в присвоении его вершинам чисел 1, 2,…, | x |, причем должно выполняться следующее условие для орграфов: если имеется дуга (x_i, x_j), то j > i (i ® j).

Рассмотрим случай для ацикличного графа:

Топологическая сортировка может быть использована:

1. При организации толкового словаря. Все понятия при этом располагаются в линейную структуру, т.е. понятия, которые используют первичные понятия (аксиоматические), находились бы ниже.

2. При организации программных систем. Здесь рассматривается совокупность взаимосвязанных процедур (одна процедура вызывает другую, та, в свою очередь, третью, и т.д.). Т.е. процедуры распределяются таким образом, чтобы не было ссылок вперед.

Рассмотрим алгоритм топологической сортировки. Идея его заключается в том, что осуществляется поиск такой вершины, из которой не выходит ни одна дуга. Такой вершине присваивается | x |. Затем эту вершину выбрасывают вместе с дугами и опять осуществляют поиск на | x | - 1, …

Введем массив LABEL размерностью | x |. Он будет обладать следующими свойствами: если вершина не выброшена, то значение LABEL(x)=0; если есть дуга (x_i, x_j), то LABEL(x _j) > LABEL(x _i).

Для поиска вершины, из которой не выходят дуги, используют алгоритм прохождения графа в глубину:

" x Î X выполнить: (Num(x)=1; LABEL(x)=0;)

C = | x | + 1;

" x Î X выполнить: если Num(x)=1, то DM(x);

Процедура DM(v);

начало

Num(V)=0;

" t Î M(V) выполнить: если Num(t)=1, то DM(t);

конец;

C = C – 1;

LABEL(V) = C;