ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»

(СПбГУТ)

Факультет инфокоммуникационных Сетей и систем (иксс)

кафедра программной инженерии и вычислительной техники (пиивт)

Лабораторная работа №4.

«Построение остовного дерева»

Дисциплина: «Алгоритмы и Структуры Данных»

Выполнил: Студент группы ИКПИ-92 Козлов Никита

Тюришев Матвей

Принял: к.т.н., доцент кафедры ПИиВТ

Дагаев А.В.

Алгоритм Краскала

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

Пример работы

Дан взвешенный неориентированный граф:

1. Выбирается ребро с минимальным весом. Минимальным весом обладает ребро 1-5. Множество выбранных вершин – {1,5}.

2. Выбирается следующее ребро с минимальным весом. Минимальным весом обладает ребро 0-5. Добавляя это ребро, цикла образовываться не будет. Ребро имеет общую вершину с множеством {1,5}, ко множеству добавляется 0 – получается множество {1,5,0}.

3. Выбирается следующее ребро с минимальным весом. Таких рёбер два – 3-2 и 2-4. Выбор среди этих двух рёбер случаен, пусть будет выбрано ребро 3-2. Ребро не имеет общих вершин с множеством {1,5,0}, создаётся второе множество {3,2}.

4. Выбирается следующее ребро с минимальным весом. Ребро с минимальным весом – 2-4. Цикл не образовывается. Общая вершина с множеством {3,2}, ко множеству добавляется 4 – получается множество {3,2,4}.

5. Выбирается следующее ребро с минимальным весом. Таких рёбер два – 0-1 и 1-4. Ребро 0-1 создаёт цикл и тем самым помечается, как непригодное.

6. Выбирается 1-4. Ребро 1-4 имеет общие вершины с обоими множествами, тем самым объединяя их. Множество выбранных вершин – {1,5,0,3,2,4} = 6, что равно количеству вершин графа. Результат построения минимального остовного дерева с весом 18 на рис.2. Всего затрачено на выполнение 6 шагов

Алгоритм Прима

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

Пример работы

Дан взвешенный неориентированный граф:

1. Выбирается случайная вершина. Пусть будет вершина 4. С вершиной 4 соединены единственным ребром вершины 2 и 1. Вершина 1 – ближайшая и выбирается, как вторая вершина. Также выбирается ребро 1-4.

2. Выбирается вершина, которая ближе всего к любой из вершин 1 или 4. Вершина 2 находится на расстоянии 6 и 4 от вершин 1 и 4 соответственно. Вершина 0 находится на расстоянии 5 от вершины 1. Вершина 5 находится на расстоянии 2 от вершины 1. Ближе всего вершина 5, она добавляется в дерево вместе с ребром 1-5.

3. Выбирается вершина, которая ближе всего к любой из вершин 1, 4 или 5. Вершина 0 находится на расстоянии 5 и 3 от вершин 1 и 5 соответственно. Вершина 2 находится на расстоянии 6 и 4 от вершин 1 и 4 соответственно. Ближе всего вершина 0, она добавляется в дерево вместе с ребром 0-5.

4. Выбирается вершина, которая ближе всего к любой из вершин 1, 4, 0 или 5. Вершина 2 находится на расстоянии 6, 6 и 4 от вершин 0, 1 и 4 соответственно. Ближе всего вершина 2, она добавляется в дерево вместе с ребром 2-4.

5. Остаётся вершина 3, соединенная единственным ребром с вершиной 2. Вершина 3 добавляется в дерево вместе с ребром 2-3. Все вершины добавлены, минимальное остовное дерево с весом 18 построено, что отображено на рис. 5. Всего затрачено на выполнение 5 шагов.

Рис.5. Минимальное остовное дерево, алгоритм Прима.

Начало

Выбор случайной вершины

Поиск ближайшей вершины к первой

Добавление в дерево вместе с ребром

Пока не собраны все вершины

Поиск ближайшей вершины к имеющимся

Добавление в дерево вместе с ребром

Конец

Рис. 6. Блок-схема алгоритма Прима.