4.2. Структуры данных для представления графов

Информацию о графах можно хранить несколькими способами:

• в виде матрицы примыканий (смежности);

• в виде списка примыканий;

• в виде двумерного массива ребер.

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

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

Если же число вершин в графе мало, то лучше воспользоваться матрицей смежности: она будет небольшой, и даже потери при хранении в матричном виде будут незначительны.

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

Различные варианты задания графа, изображенного на рис.4.3, приведены ниже.

М атрица смежности 1 2 3 4 5 6 1 0 1 0 1 1 0 2 1 0 1 0 1 1 3 0 1 0 0 0 0 4 1 0 0 0 0 1 5 1 1 0 0 0 1 6 0 1 0 1 1 0 симметрична для неориентированного графа

Список примыканий 1  2,4,5 2  1,3,5,6 3  2 4 1,6 5  1,2,6 6  2,4,5

Массив ребер 1 1 1 2 2 2 4 5 2 4 5 3 5 6 6 6

4.3. Алгоритмы обхода вершин графа

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

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

В обоих случаях мы выбираем одну из вершин графа в качестве отправной точки.

4.3.1. Обход в глубину

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

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

При выборе одной из двух вершин будем выбирать вершину с меньшей меткой.

Н апример, для графа на рис.4.4 обход в глубину будет соответствовать следующему порядку посещения вершин: 1, 2, 3, 5, 4, 8, 7 тупик; вернемся к 8 –тупик, возврат к 4 и посетим 9, 6.

Приведем пример алгоритма обхода в глубину:

DepthWay (А, N)

// А – матрица смежностей

// в стеке St хранятся номера просмотренных вершин графа

// уk - указатель стека

// Массив Nnew – Boolean признак того, что вершина просмотрена

V1; yk0; ykyk+1; St[yk]V;

Nnew (V)  false;

while yk <> 0 do // пока стек не пустой

t  St [yk] // выбор вершины из верхней точки стека

j  1; pp  False

Repeat

if A [t, J] <> 0 and Nnew[j] then pp  true

else jj+1

// найдена новая вершина рр или все вершины, связанные с данной просмотрены

until pp OR (jN);

if pp then // новая вершина

ykyk+1; S[yk]j; Nnew[j]false

else ykyk-1 // убираем номер вершины из стека

endif

endwhile

end