Задания для самостоятельной работы к разд.3.2

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

2. Дополните алгоритм Краскала возможностью выдавать все деревья покрывающего леса в случае несвязного исходного графа.

3. Реализуйте различные методы сортировок и используйте алгоритм Краскала для построения минимального (максимального) покрывающего дерева. Оцените трудоемкость программ.

4. Для построения минимальных (максимальных) покрывающих деревьев также часто используется алгоритм, предложенный Р.Примом в 1957 г. Алгоритм Прима не требует сортировки рёбер. Алгоритм заключается в следующем:

Начинаем с некоторой произвольной вершины a в заданном графе. Пусть { a, b } - ребро с наименьшим весом, инцидентное a; ребро { a, b } включается в дерево. Затем среди всех рёбер, инцидентных либо a, либо b,выбираем ребро с наименьшим (наибольшим) весом и включаем его в частично построенное дерево. В результате этого в дерево добавляется новая вершина, скажем c. Повторяя процесс, ищем наименьшее ребро, соединяющее а, b или с с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины не будут включены в дерево, то есть пока дерево не станет покрывающим.

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

5. Реализуйте алгоритм поиска в глубину и ширину. Оцените трудоемкость программ.

Для хранения последовательности вершин обхода при использовании техники поиска в глубину следует использовать стек, а поиска в ширину – очередь.

Дуги, по которым осуществляется обход вершин графа, при использовании любой техники поиска образуют ориентированное дерево с корнем в начальной вершине. Это следует из того, что начальная вершина единственная и движение в ходе поиска не осуществляется в ранее пройденные вершины. Для хранения такого дерева целесообразно использовать массив P длины n, где n – число вершин графа. Если вершины графа пронумерованы числами 1,2,…, n, то элементы массива P определяются следующим образом: P_i =0, если i – начальная вершина (корень дерева); в противном случае P_i = k, где k – вершина, предшествующая вершине i на пути из корня в вершину i.

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

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

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

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

1) P_ij – вершина, предшествующая вершине j на пути из вершины i в вершину j;

2) P_ij – вершина, следующая за вершиной i на пути из вершины i в вершину j.