Представление графов в компьютере: списки смежности, массив дуг.

n (p, q) – объема памяти для каждого представления, p – число вершин, q – число ребер. Значение характеристики n (p, q) указывается с помощью символа О, который обозначает совпадение по порядку величины (или равенство с точностью до мультипликативной константы с).

Списки смежности

Список смежности содержит для каждой вершины список смежных ей вершин.

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

N = record x: 1 ... p, n: ↑ N end record.

Массив указателей также можно представить списком.

Больше подходит для разреженных графов (у которых количество рёбер гораздо меньше чем количество вершин в квадрате).

 

рис. Пример списка смежности.

Массив дуг

Представление графа с помощью массива структур (записей), отражающего список пар смежных вершин (или, для орграфов, узлов), называется массивом ребер (массивом дуг). Для массива ребер (или дуг) n (p, q) = O (2 q).

Представление графов с помощью массива ребер (дуг) выглядит следующим образом (для графа G слева, а для орграфа D справа):

b	v	b	v
1	2	1	2
1	4	2	3
2	3	2	4
2	4	4	1
3	4	4	3

Указанные представления пригодны для графов и орграфов.

Обход графов

Обход графа – некоторое перечисление его вершин (и/или ребер). Наибольший интерес представляют обходы, использующие локальную информацию (списки смежности). Среди всех обходов наиболее известны поиск в ширину и в глубину.

Поиск в глубину

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

Таким образом, основная идея поиска в глубину – когда возможные пути по ребрам, выходящим из вершин, разветвляются, нужно сначала полностью исследовать одну ветку и только потом переходить к другим веткам (если они останутся нерассмотренными).

Алгоритм поиска в глубину

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная.

Шаг 2. Для последней помеченной как посещенная вершины выбирается смежная вершина, являющаяся первой помеченной как не посещенная, и ей присваивается значение посещенная. Если таких вершин нет, то берется предыдущая помеченная вершина.

Шаг 3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещенные (рис. 5).

Рис. 5. Демонстрация алгоритма поиска в глубину

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

Временная сложность зависит от представления графа. Если применена матрица смежности, то временная сложность равна O(n²), а если нематричное представление – O(n+m): рассматриваются все вершины и все ребра.

Поиск в ширину

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

Таким образом, основная идея поиска в ширину заключается в том, что сначала исследуются все вершины, смежные с начальной вершиной (вершина с которой начинается обход). Эти вершины находятся на расстоянии 1 от начальной. Затем исследуются все вершины на расстоянии 2 от начальной, затем все на расстоянии 3 и т.д. Обратим внимание, что при этом для каждой вершины сразу находятся длина кратчайшего маршрута от начальной вершины.

Алгоритм поиска в ширину

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная (и заносится в очередь).

Шаг 2. Посещается первая вершина из очереди (если она не помечена как посещенная). Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди.

Шаг 3. Повторяется шаг 2 до тех пор, пока очередь не пуста (рис. 6).

Рис. 6. Демонстрация алгоритма поиска в ширину