6.2. АЛГОРИТМЫ ОБХОДА ГРАФОВ

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

Отметим, что стек не обязательно должен быть одномерным массивом, особенно если речь идет об обработке изображений. Итак, граф соответствует плоскости изображения, пикселы представляются вершинами графа, причем смежные вершины соответствуют смежным пикселам. Чтобы описать некоторую точку изображения, необходимо запоминать ее координаты х, у таким образом, стек 5 оказывается массивом пар (чисел).

Алгоритм 6.1. Процедуры обработки стеков

Обозначения. I — индекс последнего элемента массива

(см. скан)

В процессе обхода необходимо использовать два типа разметки. Без потери общности можно предположить, что вначале все вершины (пикселы) помечены единицей. При введении некоторой вершины (пиксела) в стек она помечается двойкой, а после ее прохождения (в процессе обхода) — нулем. Основной алгоритм обхода связного графа (области), в котором используются указанные функции, представлены в виде алгоритма 6.2. Следует также заметить, что можно пренебрегать разметкой пикселов в случае, когда они вводятся в стек. Отказ от разметки не повлияет на «правильность» обхода (см. задачу 6.2), однако может привести к значительному увеличению размеров стека. Можно подобрать примеры, в которых для некоторого графа с вершинами размеры стека приближаются к Однако, во многих прикладных задачах граф оказывается таким, что размеры стека не создают проблем (см. подразд. 8.4.4).

Алгоритм 6.2. Основной алгоритм обхода связного графа

Обозначения. Исходными данными для процедуры являются координаты (местоположение) пиксела а в результате ее реализации определяется число соседних с ним пикселов и их местоположения, которые представляются массивом

(см. скан)

(см. скан)

Стек представляет собой структуру данных, хорошо подходящую для обхода области, однако существуют задачи, в которых необходимо удалять элементы из массива в той же последовательности, в какой они в него вводились. Соответствующая структура данных называется очередью. Функция — поставить пиксел в очередь — аналогична функции определенной для стека. Большего внимания заслуживает функция которая обеспечивает удаление точки из очереди. Эти функции описаны в алгоритме 6.3. Отметим, что для обозначения начала и конца очереди используются два отдельных индекса. Эта структура данных проста, однако, поскольку ее реализация требует определенных затрат памяти, последнюю приходится периодически перераспределять.

Более подробные сведения о методах реализации и обработки стеков и очередей читатель может найти в одной из множества имеющихся книг, посвященных алгоритмам и структурам данных (см. также разд. 6.11). Если в алгоритме 6.2 заменить стек очередью, то правильность обхода графа не нарушится, хотя порядок обхода вершин изменится. Обход графа можно осуществлять и не прибегая к использованию указанных структур данных — эта возможность связана с применением поиска с возвратом при отсутствии иных способов продолжения обхода. Все упоминавшиеся алгоритмы обхода графа подробно рассматриваются во многих учебниках

Алгоритм 6.3. Процедуры обработки очередей

Обозначения. — индекс последнего элемента массива

— индекс первого элемента массива Вначале значения обоих индексов равны первому адресу пространства, занимаемого массивом

(см. скан)