- •Введение
- •1. Начальные понятия
- •1.1. Основные определения
- •1.2. Представление графа в памяти компьютера
- •1.3. Анализ алгоритмов
- •Упражнения
- •2. Алгоритмы обхода графа
- •2.1. Поиск в ширину
- •2.2. Применение поиска в ширину
- •2.3. Поиск в глубину
- •2. 4. Применение обхода в глубину
- •Упражнения.
- •3. Кратчайшие пути
- •3.1. Алгоритм Дейкстpы
- •3.2. Кратчайшие пути между всеми парами вершин
- •Упражнения.
- •4. Остов минимального веса
- •4.1. Алгоритм Краскала
- •4. 2. Алгоритм Прима
- •4.3. Разновидности остовных деревьев
- •Упражнения.
- •5. Циклы в графах
- •5.1. Эйлеров цикл
- •5.2. Задача китайского почтальона
- •5.3. Гамильтонов цикл и задача коммивояжера
- •5.4. Классы сложности p и np
- •5.5. Решение np- полных задач
- •Упражнения.
- •6. Независимые множества и покрытия
- •6.1. Независимые множества
- •6.2. Алгоритм аппроксимации максимального независимого множества методом исключения подграфов.
- •6.3. Вершинное покрытие
- •6. 4. Паросочетания
- •Упражения
- •Список литературы
Упражнения
1. Ориентированный граф хранится в виде списков смежности. Сколько операций нужно, чтобы вычислить исходящие степени всех вершин графа? А входящие степени?
2. Укажите представление с использованием списков смежности и матрицы смежности для графа K3,3.
3. Транспонированием орграфа назовем операцию, при которой направление каждого ребра меняется на противоположное. Опишите эффективный алгоритм транспонирования орграфа, как для представления с использованием списков смежности, так и для матриц смежности. Проанализируйте время работы ваших алгоритмов.
4. Мультиграф G = (V, Е) хранится в виде списков смежных вершин. Опишите алгоритм со временем работы О(V + Е) для преобразования его в обычный граф G’ = (V’, Е’), при этом кратные ребра заменены обычными и удалены ребра-циклы.
5. Составьте таблицу в которой вычисляется время работы алгоритмов с трудоемкостью log(n), n, nlog(n), n2, n! на входных данных длиной n = 100, 1000, 104, 106, 108, 1010.
6. Предположим, что время исполнения алгоритма в наихудшем случае определяется как O( n2), возможно ли, что для некоторых входных данных это время будет O(n) ?
2. Алгоритмы обхода графа
Все основные служебные операции при работе с графами ( например, преобразование графа из одного представления в другое, распечатка или рисование графа) предполагают его систематический обход, то есть посещение каждой вершины и каждого ребра графа. Если представить лабиринт в виде графа, где ребра – проходы, а вершины – точки пересечения проходов, то любой правильный алгоритм обхода графа должен найти выход из произвольного лабиринта. Наиболее известными из таких алгоритмов являются поиск в глубину (depth first search, DFS) и поиск в ширину (breadth-first search, BFS), причем они являются базисными для многих других алгоритмов решения прикладных задач, включающих обход графа, что и будет показано в дальнейшем.
Ключевая идея обхода графа – пометить каждую вершину при первом ее посещении и хранить информацию о тех вершинах, не все ребра из которых просмотрены. В мифах Древней Греции Тесей использовал клубок ниток, который ему дала Ариадна, для обхода лабиринта, мальчик-с-пальчик помечал пройденный путь камешками или крошками, для обхода графа будут применяться перечислимые типы. В процессе обхода графа каждая его вершина будет находиться в одном из трех состояний:
неоткрытая – первоначальное состояние вершины;
открытая – вершина обнаружена, но инцидентные ей ребра не просмотрены;
обработанная (помеченная) – все ребра, инцидентные этой вершине посещены.
Понятно, что каждая вершина графа последовательно принимает все эти состояния. Первоначально открытой является только одна вершина – начало обхода графа.
Замечание: предложенные методы обходят все вершины, содержащиеся в одной компонете связности с начальной вершиной. Поэтому можно использовать любой из алгоритмов обхода для определения связности графа.
2.1. Поиск в ширину
Пусть задан граф G = (V, E) и выделена начальная вершина v. Алгоритм поиска в ширину систематически обходит все ребра графа G для «открытия» всех вершин, достижимых из v. В процессе обхода строится дерево поиска в ширину с корнем в начальной вершине, содержащее все достижимые вершины. Заметим, что расстояние (количество ребер) от корневой вершины до любой вершины этого дерева является кратчайшим.
Поиск в ширину имеет такое название, так как в процессе обхода графа помечаются все вершины на расстоянии k, прежде чем начнется обработка любой вершины на расстоянии k+1.
Алгоритм работает как для ориентированных, так и для неориентированных графов.
Идея алгоритма: все вершины, смежные с начальной, открываются, то есть помещаются в список, и получают единичную пометку. После этого начальная вершина обработана полностью и имеет пометку 2.
Следующей текущей вершиной становится первая вершина списка. Все ранее непомеченные вершины, смежные с текущей, заносятся в конец списка (становятся открытыми). Текущая вершина удаляется из списка и помечается числом 2. Процесс продолжается, пока список вершин не пуст. Такая организация списка данных называется очередью.
Рассмотрим пример. Исходный граф на левом рисунке. На правом рисунке рядом с вершинами в скобках указана очередность просмотра вершин графа. Ребра, образующие дерево поиска в ширину, выделены жирным.
Рис. 11. Просмотр вершин графа в процессе поиска в ширину.
При реализации поиска в ширину используется массив пометок Mark, массив предков Parent и очередь Q. Первоначально каждой вершине в массиве Mark соответствует значение 0, то есть вершина неоткрытая. Вершина открывается при первом посещение и ее пометка изменяется на 1. Когда все ребра, исходящие из вершины исследованы, то она считается обработанной и имеет пометку 2.
При просмотре списка вершин, смежных с текущей, открываются новые вершины. При этом их предком считается текущая вершина. Эта информация сохраняется в массиве Parent и позволяет восстановить дерево поиска в ширину. Для графа, изображенного на рисунке 11, массив предков будет иметь вид:
-
Вершина
0
1
2
3
4
5
6
7
Предок
0
0
0
0
1
2
4
6
Граф задается матрицей смежности. Код алгоритма приведен на листинге 3.
public class BreadthFirstSearchAlgm
{ // Алгоритм обхода графа «Поиск в ширину»
public void BFS(graph g)
{
int[] Mark = new int[g.kol_vershn]; // массив пометок
int[] Parent = new int[g.kol_vershn]; // массив предков
for (int i = 0; i < g.kol_vershn; i++)
{
Mark[i] = 0;
Parent[i] = 0;
}
Console.WriteLine("Вершины в порядке обхода");
Queue<int> Q = new Queue<int>(); // создание очереди
int v = 0; // задание начальной вершины
Mark[v] = 1; // пометим нач. вершину
Q.Enqueue(v); // поместим нач. вершину в очередь
Console.Write("{0} ", v);
while (Q.Count != 0) //Пока очередь не исчерпана
{ //взять из очереди очередную вершину
v = Q.Dequeue();
for (int i = 0; i < g.kol_vershn; i++)
{
if ((g.matr_smeznosti[v, i] != 0) && (Mark[i] == 0))
{ // все непомеченные вершины,
Mark[i] = 1; // смежные с текущей, помечаются
Q.Enqueue(i); // и помещаются в конец очереди
Parent[i] =v; // v – предок открытой вершины
Console.Write("{0} ", i);
}
}
Mark[v] = 2; // вершина обработана
}
Console.WriteLine();
} }
Листинг 3. Обход графа в ширину
Трудоемкость данного алгоритма O(n2), где n – количество вершин графа. Действительно, каждая вершина открывается и помещается в очередь только один раз, поэтому цикл по вершинам очереди выполняется не больше n раз. В цикл while вложен цикл по всем вершинам графа, который так же выполняется n раз. Если использовать представление графа в виде списков смежности, то трудоемкость была бы O(n+m), где m – количество ребер.