Топологическая сортировка вершин орграфа G=(V,E) заключается в присвоении его вершинам номеров 1,..,n т.о., чтобы для любой дуги этого графа выполняется условие: (Vi,Vj) єE i
Это возможно в том случае если граф не имеет контуров, является ациклическим. Топологическая сортировка может рассматриваться как процесс определения линейного порядка на множестве вершин, в которые м.б. вложен частичный порядок, заданный множеством дуг. Топологическая сортировка начинается с нахождения вершины из которой не выходит ни одной дуги. Такая вершина всегда существует, если в графе нет контуров. Ей присваивается наибольший номер N и она удаляется из графа вместе с входящими в нее дугами. Т.к. оставшийся граф также не содержит контуров, процесс повторяется и новой вершине из которой не выходят дуги, присваивается наибольший номер (n-1) и т.д.
Рассмотренный подход нетрудно реализовать на матрице смежности, но потребуется n^2 операций. Трудоемкость можно уменьшить, если исключить повторяющиеся действия по нахождению вершин, из которых не выходят дуги. Это может быть достигнуто применением поиска в глубину. Для ациклического графа эта процедура обеспечивает последовательный выбор вершин, не имеющих выходящих дуг (при возврате из рекурсии).
При реализации топологической сортировки с помощью алгоритма поиска в глубину используется массив меток вершин Label[1..n], с помощью которого моделируется удаление вершин из графа и сохраняются новые номера вершин.
Если i-ая вершина не исключена, то Label[i]=0, а если вершина удалена, то Label[i]>0. Для дуги (Vi,Vj) должно выполняться Label[i]<Label[j]. Фрагмент программы:
for i:=1 to n do begin
mark[i]:=true; Label[i]:=0;
end;
num:=n+1;
for i:=1 to n do
if mark[i] then DFS2(i);
{сама процедура сортировки}
Procedure DFS2(i:integer);
var j:integer;
begin
mark[i]:=false;
for j L(i) do
if mark[j] then DFS2(j); *
num:=num-1; Label[i]:=num; write(i);
end;
Этот же алгоритм можно использовать для обнаружения контуров в ориентированном графе по факту нахождения обратной дуги, направленной от потомка к предку в DFS дереве.
Некоторая вершина i становится просмотренной сразу же при вызове процедуры DFS2, однако новый номер (Label[i]) она получает только после завершения поиска в глубину из всех вершин, смежных i. Если в процессе этого поиска найдена некоторая вершина k, для которой mark[k]=false (уже просмотрена), но Label[k]=0 (не имеет нового номера) – это означает, что найдена обратная дуга вида (Vk,Vi). Она направлена к вершине i, из которой раннее начат, но не закончен поиск в глубину, а k – потомок i-ой вершины в DFS дереве.
Для этого добавляют строку (в позицию * программы):
else if Label[j]=0 then write (‘Цикл через вершину j’);
Опубликовал Kest
February 10 2010 17:25:25 ·
0 Комментариев ·
13155 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
