Основные определения, представление графов в памяти компьютера и способы обхода графа

Лекция 7: Алгоритмы на графах. Обход графа.

0  Введение

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

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

1  Основные определения

Граф задается множеством вершин V и множеством ребер E между этими вершинами. При этом применяется запись G=(V, E).

Часто ребру присваивается вес. Тогда граф называется взвешенным. Взвешенный граф обозначается записью G=(V, E, W).

Граф может быть ориентированным или неориентированным. В неориентированном графе ребро, соединяющее вершину u с вершиной v также соединяет вершину v с вершиной u. В ориентированном графе рассматриваются дуги, и аналогичное утверждение является неверным.

Граф, в котором |E| значительно меньше |V|², называется разреженным. Если же |E| соизмеримо с |V|², то граф называется плотным.

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

2  Представление графов

Обычно граф G=(V, E) представляется одним из двух способов:

1.  в виде списка смежных вершин;

2.  в виде матрицы смежности.

Первый способ использует массив из |V| списков. Список, стоящий на i-й позиции в этом массиве, хранит указатели на те вершины, в которые есть ребра из i-й вершины. Этот способ использует O(|V|+|E|) памяти и предпочтителен для разреженных графов.

Второй способ использует двумерный массив размером |V|². Число, стоящее в этом массиве на пересечении i-й строки и j-го столбца, показывает, есть ли ребро из i-й вершины в j-ю. Этот способ обычно используется для плотных графов.

3  Обход графа

Обработка графа так или иначе заключается в обходе графа. Обойти можно граф по-разному. Рассмотрим два алгоритма обхода графа, составляющих основу многих алгоритмов.

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

Задан граф и начальная вершина. Поиск в ширину перечисляет все вершины в порядке увеличения расстояния (количество ребер) от начальной вершины.

Для работы алгоритма применяется очередь. Вершина имеет цвет color и предшественника p.

1.  Инициализация. Создается очередь. Все вершины помечаются белым цветом. Ни у какой вершины не указан предшественник. Начальная вершина помечается в серый цвет и помещается в очередь.

2.  Обработка вершины. Из очереди извлекается вершина. Все белые вершины, которые связаны с ней, помечаются в серый цвет и помещаются в очередь. Также для каждой обнаруженной вершины запоминается ее предшественник – извлеченная из очереди вершина. Извлеченная вершина помечается в черный цвет.

3.  Завершение. Если в очереди есть вершины, перейти к шагу 2.

Алгоритм строит дерево кратчайших путей. Вершинами дерева являются вершины, достижимые из начальной (включая ее саму). Корнем дерева является начальная вершина. Дуга ставится между вершинами v и p[v]. Путь от вершины v до корня дерева является кратчайшим путем в графе от начальной вершины но вершины v.

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

Задан граф и начальная вершина. Стратегия поиска такова: идем от начальной вершины «вглубь» пока это возможно, а затем возвращаемся и ищем другой путь, пока это возможно.

1.  Инициализация. Пометить все вершины белым цветом. Присвоить v ссылку на начальную вершину.

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

Часто при поиске в глубину для каждой вершины также запоминается время обнаружения и обработки.

4  Задания и задачи

4.1  Задачи

1.  Сток

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

2.  Возведение графа в степень

Дан ориентированный граф G=(V, E) и положительное число n. Необходимо построить граф G’=(V, E’), являющийся графом G, возведенным в степень n. Множество вершин графа G=Gⁿ совпадает с множеством вершин графа G, множество ребер E’ включает множество ребер E. В E’ добавляется ребро (u, v), если существует путь из вершины u в вершину v длины n или меньшей. G¹=G.

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

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

4.  Родственные слова

Два слова называются родственными, если они различаются одной буквой. Например, слова «стог» и «слог» являются родственными.

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

Например, для того, чтобы сделать из слова «МУХА» слово «СЛОН», может быть такая цепь (словарь не показан):

МУХА

МУНА

КУНА

КАНА

КАНН

КАИН

КЛИН

КЛОН

СЛОН

5  Список литературы

Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Построение и анализ, М., МЦНМО.

В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования. Издательство Фолио. Харьков, 1997.