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 (256-257).
В прошлой статье мы начали знакомиться с широко используемыми в современной науке графами: дали ряд определений, рассмотрели большинство свойств, научились представлять графы в памяти компьютера. Что же дальше? Ну, представили мы граф в компьютере — что с ним прикажете делать?
Мы постараемся ответить на эти и многие другие вопросы. Но всему свое время. Для тех, кому еще не снятся графы в кошмарных снах, предлагается продолжение начатой нами в прошлом номере журнала темы.

Часть 4. Перевоплощения

Как мы уже говорили, эффективность того или иного алгоритма напрямую зависит от способа представления объекта, от выбора наиболее выгодной структуры данных для его описания. А если случится так, что выбирать нам не придется? Как говорится, «не так завжди трапляється, як гадається». Давайте попробуем научиться переводить граф из одной системы данных в другую.

1. Пускай на входе есть переменная типа «указатель на динамический список ребер». Давайте переведем его в матрицу смежностей. Так как мы не сможем рассмотреть все случаи наименований вершин, разберемся с простейшим из них. Допустим, что каждая вершина графа имеет свой порядковый номер, то есть множество вершин графа является некоторым конечным подмножеством натуральных чисел. Что требуется для перевода?

узнать число N — количество вершин в графе. Осуществляется это посредством нахождения максимального значения (номера вершины) среди элементов списка по двум из полей: начала и конца ребра;

составить массив C размера N*N;

инициализировать массив: обнулить все его элементы (если на входе обычный граф), присвоить всем элементам значение (-1) (в случае сети);

проходить список ребер и заносить одновременно в ячейки G(i,j) и G(j,i) значения веса (длины) ребра [i,j] (в случае сети) или 1 в (случае обычного графа).

Примечание. Если мы хотим составить матрицу G* в случае с орграфом, то значения веса или единица заносятся лишь в ячейку G*(i,j) при наличии дуги (i,j).

Давайте напишем процедуру перевода список ребер в матрицу смежностей:

2. А теперь произведем обратный процесс: имея матрицу смежностей, получим список ребер.

Алгоритм следующий:

а). В случае с неориентированным графом работаем только с половиной массива, то есть до главной диагонали (зачем нам повторяющиеся ребра в списке?)

б). В случае с орграфом, который задан матрицей C*, работаем со всем массивом.

Проходим элементы «рабочей области» массива (в зависимости от вышеописанных вариатов) и добавляем элемент ребро (дугу) [i,j] в список, если С(i,j)=1 (C(i,j)0 — в сети).

Рассмотрим процедуру для невзвешенного неориентированного графа:

Имея на входе матрицу типа С* для ориентированного графа, основной цикл процедуры Interpretation2 примет вид:

3. А вот получить список смежностей в виде массива записей из динамического списка ребер будет немного сложнее. Шаги алгоритма записываются приблизительно так:

найти максимальный номер вершины, чтобы определить количество вершин в графе (аналогично алгоритму процедуры Interpretation1);

для каждого i — номера вершины — просматривать список и находить ребра, началом или концом которых является вершина i. Если такое ребро имеется в списке, j увеличиваем на 1, увеличиваем счетчик Count на 1 и добавляем смежную для i вершину в массив G[i].List[j].n:

4. Ну, и, наконец, для полного счастья сделаем матрицу смежностей из списка смежностей. Алгоритм немудреный:

инициализировать массив N*N;

для каждой вершины і просматриваем смежные с ней и в ячейку массива C(i, G[i].List[j].n) записываем 1 (G[i].List[j].w — для взвешенного):

Вот мы запаслись набором инструментов, необходимым для осуществления разных алгоритмов.

Часть 5. Обход графа и достижимость вершин

Существует два основных способа обхода графов: поиск в глубину и поиск в ширину. Поиск в графе означает обход вершин графа начиная с некоторой из них. Методы обхода отличаются порядком посещения вершин. Дадим определение компонент связности графа: это такие непересекающиеся между собой подмножества вершин графа, что вершина i достижима из вершины j только в том случае, когда вершины i и j принадлежат одной компоненте связности.

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

начальная вершина, с которой начинается путь, считается посещенной;

из текущей вершины продвигаемся в смежную с ней еще не посещенную, если таковая имеется;

если таковой не имеется, возвращаемся в вершину, из которой мы попали в текущую; если же мы после этого оказались в начальной вершине, значит, перебор вершин окончен. Все вершины данной компоненты связности посещены.

Рассмотрим пример:

находимся в вершине 1. Она посещена;

идем в смежную с вершиной 1 непосещенную вершину 2;

идем в смежную с вершиной 2 непосещенную вершину 3;

идем в смежную с вершиной 3 непосещенную вершину 4;

все смежные с вершиной 4 вершины уже — посещенные. Возвращаемся в вершину, из которой мы попали в 4 — в вершину 3;

все смежные с вершиной 3 уже — посещенные. Возвращаемся в вершину, из которой мы попали в 3 — вершину 2;

идем в смежную с вершиной 2 еще не посещенную вершину 6;

все смежные с вершиной 6 уже — посещенные. Возвращаемся в вершину, из которой мы попали в 6 — вершину 2;

все смежные с вершиной 2 уже — посещенные. Возвращаемся в вершину, из которой мы попали в 2 — вершину 1;

идем в смежную с вершиной 1 еще не посещенную вершину 5;

все смежные с вершиной 5 уже — посещенные. Возвращаемся в вершину, из которой мы попали в 5 — вершину 1;

все смежные с вершиной 1 уже — посещенные. Причем, вершина 1 является начальной. Алгоритм закачивает свою работу: все вершины, достижимые из начальной, посещены.

На рисунке выделенными линиями ребер виден наш маршрут. Таким образом, порядок посещения вершин следующий: 1, 2, 3, 4, 6, 5.

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

Здесь используется тип Type ArBool: array[1..N] of Boolean:

По окончанию работы алгоритма на выходе мы имеем массив, ячейки которого содержат значения True или False: если IsVisited[i]=True, значит, вершину i мы посетили, False — в противном случае. Данный алгоритм очень полезен для проверки достижимости вершины из данной. Запустим процедуру DepthSearch1 с входящим параметром k — начальной вершины, и получим массив IsVisited. Обратившись к любому элементу массива, мы легко узнаем, достижима ли вершина i из начальной или из любой другой, принадлежащей компоненте связности, которую мы обработали:

А теперь предположим, что мы хотим осуществить поиск в глубину, посетив абсолютно все вершины графа. Отличается он лишь тем, что поочередно обходятся компоненты связности. В нашем случае порядок обхода будет следующим: 1, 4, 8, 2, 3, 5, 6, 7, 9.

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

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

Порядок обхода будет таким: 1, 2, 3, 4, 5, 6.

посетили вершину 1;

посетили смежную с 1 вершину 2;

посетили смежную с 1 вершину 3;

посетили смежную с 1 вершину 4;

посетили смежную с 1 вершину 5.

все смежные с 1 вершины посещены. Переходим к рассмотрению непосещенных вершин, смежных с 2;

посетили смежную с 2 вершину 6. Все вершины посещены.

Попробуем реализовать алгоритм поиска в ширину программно:

Данный алгоритм требует использования очереди — структуры данных, в которой новый элемент добавляется в конец, а первый извлекается из ее начала. Так, начальная вершина добавляется в конец очереди. Пока стек не опустеет, мы просматриваем первую вершину в очереди и обходим все непосещенные, смежные с ней. Удаляем первую вершину из начала очереди. При посещении каждая вершина добавляется в конец. Такой процесс изменяет порядок обхода вершин — мы продвигаемся равномерно во все стороны.

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

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






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

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

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





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