[ главная ]   [ рейтинг статей ]   [ справочник радиолюбителя ]   [ новости мира ИТ ]



Ответов: 0
25-02-12 07:01







   Web - программирование
PHP


ASP






XML



CSS

SSI





   Программирование под ОС











   Web - технологии








   Базы Данных









   Графика






Данные




Программирование под ОС / Алгоритмы /

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

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

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



Комментарии

bgbvmnwi
29-07-2011   
vb4hX8 <a href="http://lqnqhnqqddfa.com/">lqnqhnqqddfa</a>

xkjidnchc
26-07-2011   
SCGDgp , [url=http://jbucapvlngtv.com/]jbucapvlngtv[/url], [link=http://bbeyeegmlvqk.com/]bbeyeegmlvqk[/link], http://cmidjtxgavxp.com/

pexzgfoguea
26-07-2011   
96HQZg <a href="http://imkygqvsenuu.com/">imkygqvsenuu</a>

Alla
26-07-2011   
Wow, thats a really celver way of thinking about it!

 Ваш комментарий к данному материалу будет интересен нам и нашим читателям!



Последние статьи: Программирование под ОС / Алгоритмы /

Основные понятия теории алгоритмов - часть первая
09-04-2009   

Алгоритмом часто называют конечную совокупность инструкций для решения некоторого класса задач. Это определение неформально, так как с его помощью нельзя однозначно ответить на вопросы, что такое совокупность инструкций и некоторый класс задач... подробнее

Кол. просмотров: общее - 3059 сегодня - 0

Основные понятия теории алгоритмов - часть вторая
09-04-2009   

В современной математике алгоритмами принято называть конструктивно задаваемые соответствия между словами в абстрактных алфавитах. Это определение, в свою очередь, использует два понятия – понятие абстрактного алфавита и слов в таком алфавите... подробнее

Кол. просмотров: общее - 3102 сегодня - 0

Основные понятия теории алгоритмов - часть третья
09-04-2009   

К наиболее простым алфавитным операторам относятся так называемые посимвольные отображения. Последнее состоит в том, что каждый символ входного слова алфавита А заменяется некоторым символом выходного алфавита В... подробнее

Кол. просмотров: общее - 3153 сегодня - 0

Основные понятия теории алгоритмов - часть четвертая
09-04-2009   

Понятие алфавитного оператора является чрезвычайно общим. К нему фактически сводятся или могут быть сведены любые процессы преобразования информации, поскольку символам алфавита можно поставить в соответствие объекты произвольной природы... подробнее

Кол. просмотров: общее - 2852 сегодня - 0

Оценка сложности алгоритмов
09-04-2009   

С каждым алгоритмом обычно связывается интуитивное представление о их сложности, основанное на оценке количества необходимых преобразований слов, а также количества и длины самих слов... подробнее

Кол. просмотров: общее - 3057 сегодня - 0



  WWW.COMPROG.RU - 2009-2012 | Designed and Powered by Zaipov Renat | Projects