CFA LogoCFA Logo Computer
Новости Статьи Магазин Прайс-лист Драйвера Контакты
Новости
RSS канал новостей
В конце марта компания ASRock анонсировала фирменную линейку графических ускорителей Phantom Gaming. ...
Компания Huawei продолжает заниматься расширением фирменной линейки смартфонов Y Series. Очередное ...
Компания Antec в своем очередном пресс-релизе анонсировала поставки фирменной серии блоков питания ...
Компания Thermalright отчиталась о готовности нового высокопроизводительного процессорного кулера ...
Компания Biostar сообщает в официальном пресс-релизе о готовности флагманской материнской платы ...
Самое интересное
Программаторы 25 SPI FLASH Адаптеры Optibay HDD Caddy Драйвера nVidia GeForce Драйвера AMD Radeon HD Игры на DVD Сравнение видеокарт Сравнение процессоров

АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2003 ГОД

В графском парке

Юрий ДОВГАНЬ freeyuran@ukrpost.net

Продолжение, начало см. в МК № 33-34, 38, 43, 46 (256-257, 261, 266, 269).
Не так давно мы с вами, уважаемые читатели, начали знакомиться с элементами теории графов. Мы проверили на деле списки смежностей и ребер, а также матрицы инцидентностей, используя их в алгоритмах решения задач различного класса. Как показала практика, на этом перечисление списка возможных задач для программиста не заканчивается. Наоборот, все только начинается!

В предыдущей статье мы сумели рассмотреть и реализовать довольно серьезный алгоритм, основанный на методе Минти, — алгоритм решения задачи о самых коротких путях в сети. Оказалось, этот метод не является единственным в своем роде. Алгоритм Флойда может с не меньшей эффективностью «обрабатывать» задачу о кратчайших маршрутах в сетях. Насколько удобнее его использовать, покажет практика. А пока будем постепенно с ним знакомиться.

Часть 10. Алгоритм Флойда

Напоминаю, в методе Минти мы довольно ловко сумели использовать структуру списка ребер. Алгоритм Флойда же относится к классу «матричных» алгоритмов: основной структурой данных здесь являются матрицы смежностей или же матрицы весов. Матрицу весов определим следующим образом:

В первом случае G[i,j] равняется весу (длине) существующего ребра (дуги). Во втором случае имеются в виду элементы G[i,i] (вариант наличия петель мы исключаем). И, наконец, в третьем случае длина несуществующего ребра приравнивается к бесконечности. Как обычно, проиллюстрируем вышесказанное на примере. Рассмотрим неориентированный граф (сверху ребер указываются их длины):

Его матрица весов примет следующий вид:

Как видим, матрица G симметрична относительно главной диагонали, что говорит о неориентированности графа (это мы помним, это мы знаем :-)). К примеру, G[2,4]=5: ребро [2,4] имеет длину (вес) 5. G[3,5]=<4>: ребра [3,5] не существует, поэтому расстояние между вершинами 3 и 5 оценивается как бесконечное. Вопрос, как представить бесконечность в Паскале, сразу забудьте на время. С этим мы еще столкнемся :-).

Итак, в ходе работы алгоритма нам понадобится 2 дополнительных массива, исключая входящую матрицу весов. В процессе будут использоваться матрица длин кратчайших путей и матрица самих путей. Исходя из предположения связности графа, определим эти два понятия. Матрица длин кратчайших путей — это массив размерностью в количество вершин (N=|V|), где элемент L[i,j]=length{i,…,j}, то бишь длине (весу) маршрута (!), который начинается в вершине i и закачивается в j. Например, для вышеуказанного примера графа элемент L[5,2]=6 (на рисунке видно, что кратчайший путь из вершины 5 в вершину 2 будет проходить по ребрам [5,4], [4,1]; сумма их длин равна 6). Заметим, что поскольку мы будем рассматривать связные графы (или компоненты связности по отдельности), то «бесконечности» в матрице кратчайших путей исчезнут: все вершины могут быть соединены определенным маршрутом.

Матрица путей тоже имеет размерность N=|V|, а ее элементы определяются следующим образом: элемент W[i,j] равняется номеру следующей после i вершины в кратчайшем маршруте от вершины i к вершине j. Перевожу на русский язык. Смотрим на наш граф. Для него, к примеру, W[5,3]=4. Это значит, что следующей вершиной после 5-й на пути к 3-й будет вершина с номером 4. Идем дальше: W[4,3]=2, W[2,3]=3. Имеем путь: {5, 4, 2, 3} — кратчайший маршрут, который соединяет вершину 5 с вершиной 3. Кажется, это несложно.

Теперь о главном. Как будет выглядеть наш алгоритм? Имея на входе матрицу весов G, которая представляет соответствующий взвешенный граф, инициализируем массивы L и W следующим образом:

1) L[i,j]=G[i,j], для всех i=1,2,..,N; j=1,2,…,N;

2) W[i,j]=j, если G[i,j]<? и W[i,j]=0, если G[i,j]= ?

В процессе алгоритма матрицы L и W будут претерпевать изменения. Для этого введем целочисленную переменную m, которая будет отображать номер итерации. Выходит, что Lm — это не L в степени m, а матрица L во время m-й итерации. Причем элемент Lm[i,j] будет совпадать со значением кратчайшего расстояния маршрута между вершинами i и j с промежуточными вершинами из множества [1..m]. Матрица Lm+1 будет строиться следующим образом: Lm+1[i,j]=min{Lm[i,j], Lm[i,m+1]+Lm[m+1,j]}. При этом мы пробегаем все вершины m, i, j и проверяем: в том случае, если L[i,j]>L[i,m]+L[m,j] (пройти из i в j через m быстрее, чем напрямую), то изменяем значение L[i,j] на L[i,m]+L[m,j].

Другими словами, на (m+1)-й итерации мы ищем кратчайший путь из i в j с промежуточными вершинами [1..m+1]. Если этот маршрут не содержит вершину m+1, то L(m+1)[i,j]=Lm[i,j]. А вот если все-таки содержит (m+1)-ю вершину, то его можно разделить на две части: от i до (m+1) и от (m+1) до j.

Для запоминания путей следует в случае L[i,j]>L[i,m]+L[m,j] изменять также значение W[i,j] на W[m,j]. Так формируется матрица путей.

Одной из особенностей алгоритма Флойда является возможность работы с отрицательными весами ребер (дуг). Поэтому множество, из которого длины ребер могут принимать значение, расширяется на всю действительную ось (числа из ?????[тут какая-то хрень была вставлена, похожая на готическую R]). При таких условиях в случае обнаружения вершины i при Lm[i,m]+Lm[m,i]<0 получаем факт наличия в графе цикла отрицательной суммарной длины, который проходит через вершину i. В таком случае алгоритм скоропостижно завершает свою работу: решения задача не имеет.

Перед составлением кода процедуры заметим, что алгоритм Флойда работает как с ребрами, так и с дугами:

Процедура ShowWay выводит на экран кратчайший маршрут, соединяющий вершины u и v. Идея процедуры лежит в определении матрицы путей, о которой речь шла в начале статьи. Чтобы узнать длину этого пути, достаточно вывести значение элемента L[u,v].

Теперь о бесконечности! Разумеется, в Паскале мы не можем использовать это понятие. Поэтому, в зависимости от условий, заданных графов, нам придется подобрать значку ? стоящую «замену». К примеру, мы пишем программу для графов, не содержащих отрицательные веса ребер. В таком случае бесконечность можно заменить на определенное отрицательное число. Я в своей программе использовал число (-1), которое должно находиться везде вместо значка ? в нашей программе. Если все-таки отрицательные веса имеются, выберите довольно большое по модулю отрицательное число, которое и в помине не встречается в вашем графе. Опять-таки придется вписать его во всех местах, где есть бесконечность. Теперь это уже ясно как пить дать :-).

Весомым преимуществом алгоритма Флойда является тот факт, что матрица длин кратчайших путей отображает минимальные расстояния между всеми (!) парами вершин, в то время как метод Минти нужно было «запускать» для каждой пары, не содержащей общее начало, отдельно.

Часть 11. Эйлеровы циклы и эйлеровы графы

Читатель должен помнить, что в первой статье невольно «проскользнуло» понятие цикла как замкнутого маршрута, у которого начальная и конечная вершины совпадают. Как оказалось, циклы тоже бывают разными. Одним из классов циклов является так называемый эйлеров цикл, названный в честь известного математика — дядьки Эйлера, который и заварил эту кашу с графами. А именно, эйлеров цикл — это цикл, который содержит каждое ребро графа, причем ровно по одному разу. И, соответственно, граф, содержащий эйлеров цикл, называется эйлеровым. Эйлеров граф мы можем начертить, не отрывая карандаша от бумаги. Так, например, все многоугольники будут иметь свойство эйлерового цикла, в то время как прямоугольник с обеими своими диагоналями эйлеров цикл образовать не сможет.

Существует ли четкое правило, позволяющее определить «эйлеровость» графа :-)? К счастью, да! И формулируется сие правило в теореме Эйлера (критерий наличия в графе эйлерового цикла), которая гласит: в графе существует эйлеров цикл тогда и только тогда, когда все вершины графа имеют четную степень. Напоминаю, что степенью вершины графа называется количество ребер, ей инцидентных. Имея хотя бы одну вершину степени 3, к примеру, мы уже не получим эйлеров цикл.

Такой цикл (на рисунке) эйлеровым уже не будет: верхняя вершина имеет степень 3. Если кто-то сможет доказать обратное, пройдя по каждому ребру ровно один раз и нарисовав точно такой же граф — бегом за Нобелевской премией :-).

Осталось только оформить процесс нахождения эйлеровых циклов в виде алгоритма и соответствующего ему кода.

Пусть на входе есть граф, который удовлетворяет условию теоремы Эйлера. Во всяком случае, мы сможем убедиться в эйлеровости графа в ходе работы алгоритма. Также на вход подается вершина, с которой мы начинаем обход. Осуществляя поиск в глубину, мы удаляем ребра. Обнаружив «промежуточный» подцикл графа, мы добавляем текущую вершину (которая замыкает обнаруженный подцикл) в стек. От удаления ребер этого цикла из графа кратность степеней вершин не изменится. Продвигаемся дальше, пока все ребра не будут удалены. Вершины стека дадут нам эйлеров цикл в нужном порядке. Вышеописанный алгоритм носит название алгоритма Флёри. Посмотрим как это будет выглядеть на деле.

Реализуем алгоритм с помощью рекурсивной процедуры:

Давайте рассмотрим пример.

С началом в вершине 1, пользуясь поиском в глубину, мы получим следующий порядок обхода вершин (удаления ребер):

[1,2], [2,3], [3,1], [3,4], [4,5], [5,2], [2,6], [6,5], [5,3].

В то время как содержание стека (эйлеров цикл как последовательность вершин) следующее:

1, 3, 5, 6, 2, 5, 4, 3, 2, 1.

Можно заметить, что эйлеров цикл содержит каждое ребро ровно по одному разу и проходит по всем ребрам графа. Каждая вершина имеет четную степень — значит, граф эйлеров.

(Продолжение следует)

Рекомендуем ещё прочитать:






Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:

RSS
Комментарий:
Введите символы или вычислите пример: *
captcha
Обновить





Хостинг на серверах в Украине, США и Германии. © www.sector.biz.ua 2006-2015 design by Vadim Popov