Лекция № 4

Тема: «Алгоритмы на графах»

План лекции

1. Понятие графа

2. Топологическая сортировка графа

3. Понятие дерева

4. Пирамидальная сортировка дерева

1. Понятие графа

Рассмотрим две задачи.

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?

Решение: Занумеруем последовательно клетки доски:

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

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

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

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.

Граф G – это упорядоченная пара (V, E), где V – непустое множество вершин, E – множество пар элементов множества V, называемое множеством ребер. Упорядоченная пара элементов из V называется дугой. Если все пары в Е упорядочены, то граф называется ориентированным (орграфом).

Если дуга e ведет от вершины v1 к вершине v2, то говорят, что дуга e инцидентна вершине v2, а вершина v2 являются смежной вершине v1. В случае неориентированного графа ребро e является инцидентной обеим вершинам v1 и v2, а сами вершины – взаимно смежными.

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

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

Петля – дуга, соединяющая некоторую вершину сама с собой.

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

Выбор структуры данных для хранения графа в памяти имеет принципиальное значение при разработке эффективных алгоритмов. Рассмотрим два матричных и три списочных представления графа:

– матрица смежности;

– матрица инцидентности;

– списки смежных вершин;

– список ребер;

– списки вершин и ребер.

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

Матрица смежности – это двумерный массив размером n×n.

При этом

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

Пространственная сложность этого способа V(n)~O(n2). Способ очень хорош, когда надо часто проверять смежность или находить вес ребра по двум заданным вершинам.

Матрица инцидентности – это двумерный массив размером n×m.

Пространственная сложность этого способа V(n, m)~O(n×m). Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».

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

Пространственная сложность этого способа Vmax(n)~O(n2). Хранение списков в динамической памяти позволяет сократить объем расходуемой памяти, так как в этом случае не будет резервироваться место под n соседей для каждой вершины. Можно и сам массив представить в виде динамического списка, но это не имеет особого смысла, так как граф обычно является статичной (неизменяемой) структурой.

Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин, смежных с x».

Список ребер – это одномерный массив размером m, содержащий список пар вершин, инцидентных с одним ребром графа.

Пространственная сложность этого способа V(m)~O(m). Этот способ хранения графа особенно удобен, если главная операция, которой чаще всего выполняется, это перечисление ребер или нахождение вершин и ребер, находящихся в отношениях инцидентности.

Рисунок 1 – Граф и его реализация

Граф можно представить также в виде списочной структуры, состоящей из списков двух типов – списки вершин и списков ребер. Пространственная сложность этого способа V(n, m)~O(n+m).

2. Топологическая сортировка графа

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

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

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

↑ Пример ориентированного неотсортированного графа, к которому применима топологическая сортировка

Из рисунка видно, что граф не отсортирован, так как ребро из вершины с номером 4 ведет в вершину с меньшим номером (2).

Существует несколько способов топологической сортировки — из наиболее известных:

· Алгоритм Демукрона

· Метод сортировки для представления графа в виде нескольких уровней

· Метод топологической сортировки с помощью обхода в глубину

Последний метод наиболее популярен, нагляден и прост в реализации.

Алгоритм

Поиск в глубину или обход в глубину (англ. Depth-first search, сокращенно DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Запускаем обход в глубину, и когда вершина обработана, заносим ее в стек. По окончании обхода в глубину вершины достаются из стека. Новые номера присваиваются в порядке вытаскивания из стека.

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

Рассмотрим данный алгоритм на примере:

↑ Имеем бесконтурный ориентированный граф. Изначально все вершины белые, а стек пуст. Начнем обход в глубину с вершины номер 1.

↑ Переходим к вершине номер 1. Красим ее в серый цвет.

↑ Существует ребро из вершины номер 1 в вершину номер 4. Переходим к вершине номер 4 и красим ее в серый цвет.

↑ Существует ребро из вершины номер 4 в вершину номер 2. Переходим к вершине номер 2 и красим ее в серый цвет.

↑ Из вершины номер 2 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 2 в черный цвет и кладем ее в стек.

↑ Существует ребро из вершины номер 4 в вершину номер 3. Переходим к вершине номер 3 и красим ее в серый цвет.

↑ Из вершины номер 3 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 3 в черный цвет и кладем ее в стек.

↑ Из вершины номер 4 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 1. Красим вершину номер 4 в черный цвет и кладем ее в стек.

↑ Из вершины номер 1 нет рёбер, идущих не в черные вершины. Красим её в черный цвет и кладем в стек. Обход точек закончен.

↑ По очереди достаем все вершины из стека и присваиваем им номера 1, 2, 3, 4 соответсвенно. Алгоритм топологической сортировки завершен. Граф отсортирован.

Применение

Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов.

Реализация

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

vector<int> g[MAXN]; // граф

bool used[MAXN];

vector<int> ans;

void dfs (int v) {

used[v] = true;

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (!used[to])

dfs (to);

}

ans.push_back (v);

}

void topological_sort() {

for (int i=0; i<n; ++i)

used[i] = false;

ans.clear();

for (int i=0; i<n; ++i)

if (!used[i])

dfs (i);

reverse (ans.begin(), ans.end());

}

Здесь константе следует задать значение, равное максимально возможному числу вершин в графе.

Основная функция решения — это topological_sort, она инициализирует пометки обхода в глубину, запускает его, и ответ в итоге получается в векторе .

3. Понятие дерева

Дерево является одним из важных и интересных частных случаев графа, поэтому оно рассматривается отдельно от графов других видов.

Деревом называется орграф, для которого:

1) существует узел, в который не входит ни одной дуги (корень);

2) в каждую вершину, кроме корня, входит одна дуга.

Вершины дерева подразделяют на следующие три группы:

– корень – вершина, в которую не входит ни одной дуги;

– узлы – вершины, в которые входит одна дуга и выходит одна или более дуг;

– листья – вершины, в которые входит одна дуга и не выходит ни одной дуги.

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

Выделяют уровни дерева. На первом уровне дерева может быть только одна вершина – корень, на втором – потомки корня, на третьем – потомки потомков корня и т. д.

Поддеревом называется вершина со всеми ее потомками.

Высотой поддерева будем считать максимальную длину цепи y1, …,yn его вершин такую, что yi+1 – потомок yi для всех i. Высота пустого дерева равна нулю, высота дерева из одного корня – единице.

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

По величине степени дерева часто различают два типа деревьев:

– двоичные – степень дерева не более двух;

– сильноветвящиеся – степень дерева произвольная.

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

При таком способе представления дерева обязательно следует сохранять указатель на вершину, являющуюся корнем дерева.

Обходы деревьев

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

– в прямом порядке;

– в обратном порядке;

– в симметричном (внутреннем) порядке.

Все три способа обхода рекурсивно можно определить следующим образом:

1) если дерево Tree является пустым деревом, то в список обхода заносится пустая запись;

2) если дерево Tree состоит из одной вершины, то в список обхода записывается эта вершина;

3) если Tree – дерево с корнем n и поддеревьями Tree1, Tree2, …,Treek, то:

– при прохождении в прямом порядке сначала посещается корень n, затем в прямом порядке вершины поддерева Tree1, далее в прямом порядке вершины поддерева Tree2 и т. д. Последними в прямом порядке посещаются вершины поддерева Treek;

– при прохождении в обратном порядке сначала посещаются в обратном порядке вершины поддерева Tree1, далее последовательно в обратном порядке посещаются вершины поддеревьев Tree2, …, Treek. Последним посещается корень n;

– при прохождении в симметричном порядке сначала посещаются в симметричном порядке вершины поддерева Tree1, далее корень n, затем последовательно в симметричном порядке вершины поддеревьев Tree2,…, Treek.

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

Спецификация двоичных деревьев

Двоичные (бинарные) деревья – это деревья со степенью не более двух (рис. 6).

По степени вершин двоичные деревья бывают:

– строгие – вершины дерева имеют степень нуль (у листьев) или два (у узлов);

– нестрогие – вершины дерева имеют степень нуль (у листьев), один или два (у узлов).

В общем случае на k-м уровне двоичного дерева может быть до 2^k–1 вершин.

Двоичное дерево, содержащее только полностью заполненные уровни (т. е. 2^k–1 вершин на каждом k-м уровне), называется полным.

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

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

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

Адрес любой вершины в массиве вычисляется как

где k – номер уровня вершины; i – номер на уровне k в полном двоичном дереве. Адрес корня будет равен единице. Для любой вершины, имеющей индекс j в массиве, можно вычислить адреса левого и правого потомков:

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

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

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

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

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

4. Пирамидальная сортировка дерева

Метод сортировки простым выбором основан на повторном выборе наименьшего ключа среди n элементов, затем средиn-1элементов, и т.д. Соответственно поиск наименьшего элемента из n элементов потребуетn-1сравнений. Направление улучшения сортировки – получать от каждого прохода больше информации, чем просто указание на один наименьший элемент.

Пирамида это бинарное дерево (каждый узел которого имеет два дочерних узла) высоты k, в котором:

- все узлы имеют глубину k или k-1- дерево сбалансированное;

- при этом уровень k-1 полностью заполнен, а уровень k заполнен слева направо;

- выполняется "свойство пирамиды": каждый дочерний элемент меньше, либо равен родителю.

Как хранить пирамиду? Наименее хлопотно - поместить ее в массив. Соответствие между геометрической структурой пирамиды как дерева и массивом устанавливается по следующей схеме:

−в A[0] хранится корень дерева;

−левый и правый сыновья элемента A[i] хранятся, соответственно, в A[2i+1] и A[2i+2]. Схема хранения проиллюстрирована на рисунке.

Пирамидальная сортировка состоит из двух фаз:

1.Построение пирамиды (просеивание).

2.Фаза сортировки.

Начать построение пирамиды можно с A[k]...A[n], k = [size/2]. Эта часть массива удовлетворяет свойству пирамиды, так как не существует индексов i, j: i = 2i+1 (или j = 2i+2) просто потому, что такие i, j находятся за границей массива. Другими словами работа начинается с того узла, у которого имеется хотя бы один дочерний узел (см. рис. 5.3).

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

Чтобы при добавлении элемента сохранялась пирамидальность, будем использовать следующую процедуру расширения пирамиды A[i+1]..A[n] на элемент A[i] влево:

1.Смотрим на сыновей слева и справа - в массиве это A[2i+1] и A[2i+2] и выбираем наибольшего из них.

2.Если этот элемент больше A[i] - меняем его с A[i] местами и идем к шагу 2, имея в виду новое положение A[i] в массиве. Иначе конец процедуры.

Итак, задача построения пирамиды из массива успешно решена. Как видно из свойств пирамиды, в корне всегда находится максимальный элемент. Отсюда вытекает алгоритм фазы 2:

1. Берем верхний элемент пирамиды A[0]...A[n] (первый в массиве) и меняем с последним местами. Теперь "забываем" об этом элементе и далее рассматриваем массив A[0]...A[n-1].Для превращения его в пирамиду достаточно просеять лишь новый первый элемент.

2. Повторяем шаг 1, пока обрабатываемая часть массива не уменьшится до одного элемента.

Очевидно, в конец массива каждый раз попадает максимальный элемент из текущей пирамиды, поэтому в правой части постепенно возникает упорядоченная последовательность.

Вычислительные затраты пирамидальной сортировки составляют N log(N) .

Контрольные вопросы

1. Что относится к нестатистическим структурам данных

2. Понятие графов

3. Понятие деревьев

4. Поиск, добавление элементов в графе

5. Поиск, добавление элементов в двоичных деревьях

6. Матрица смежности и инцидентности в графе

7. Списочное представление двоичных деревьев

8. Опишите алгоритм обхода графа

9. Опишите алгоритм топологической сортировки графа

10. Опишите алгоритм обхода дерева и пирамидальной сортировки