Практическая работа №2
Базовые алгоритмы на графах.
1. Цель работы
Реализовать и проверить на тестовом примере базовый алгоритм на графе. Сравнить быстродействие реализованного алгоритма на специальных графах.
2. Порядок выполнения работы
1.Самостоятельно составить и визуализировать граф (для алгоритмов под номерами 2-4 (см. таблицу 2.1) создается взвешенный граф, количество вершин должно быть не менее 5, составить в виде любого представления, например, матрица смежности, список ребер, массив записей и т.п.).
2.Реализовать выбранный из таблицы 2.1 базовый алгоритм средствами ЭВМ.
3.Выполнить отладку работы алгоритма на графе, созданном по пункту 1
порядка выполнения практической работы.
4.Написать подпрограмму, реализующую создание графа,
предложенного в таблице 2.2 типа (для алгоритмов под номерами 2-4 (см. таблицу 2.1) создается взвешенный граф, вариант решетки получить у преподавателя, представление любое, например, матрица смежности, список ребер, массив записей и т.п.).
5.Построить график зависимости быстродействия (среднего времени выполнения) алгоритма от количества узлов в графе, полученного в пункте 4 порядка выполнения практической работы (без учета времени создания графа).
3. Содержание отчета
1.Цель работы.
2.Изображение и представление графа, созданного в пункте 1 порядка выполнения п/р.
3.Описание заданного по варианту базового алгоритма (например, псевдокод с описанием, или блок-схема с описанием, или полное описание и т.п.).
4.Применение «на бумаге» заданного алгоритма для графа, созданного в пункте 1 порядка выполнения п/р (Описание работы алгоритма на конкретном примере).
5.Описание (листинг, комментарии с описанием использованных переменных) и результаты выполнения разработанных программ.
6.Изображение и представление графа, созданного в пункте 4 порядка выполнения п/р (размер графа выбрать произвольно – не менее 9, не более 36).
7.График быстродействия алгоритма, построенный по пункту 5 порядка выполнения п/р.
8.Выводы (описание результатов оценки быстродействия алгоритма, проблемы при реализации, примеры применения алгоритма для решения реальных задач и т.п.).
Таблица 2.1 – Список базовых алгоритмов
№
Наименование алгоритма
варианта
1Алгоритм поиска компонент связанности
2Алгоритм поиска минимального остовного дерева (алгоритм Прима)
3Алгоритм поиска минимального остовного дерева (алгоритм Крускала (или Краскала))
4 |
Алгоритм Дейкстры |
|
|
5 |
Алгоритм поиска кратчайшего маршрута (поиск в глубину) |
|
|
6 |
Алгоритм поиска кратчайшего маршрута (поиск в ширину) |
|
|
7 |
Алгоритм гомеоморфного сжатия графа |
|
|
8 |
Нахождение метрики Жаккара между всеми парами вершин |
|
|
Таблица 2.2 – Тип графа для анализа алгоритмов
№
Исходные данные*
варианта
1Правильная квадратная решетка
2Правильная треугольная решетка
3Правильная шестиугольная решетка
*Алгоритмы создания матриц смежности заданных видов графов описан в Приложении 1.
Приложение 1
Пример создания правильной квадратной решетки
Псевдокод алгоритма заполнения матрицы смежности графа вида «правильная квадратная решетка размера M на M»:
1)Создать нулевую квадратную матрицу Matrix размера M2 на M2;
2)Для каждой вершины V:
-номер строки: R = V \ M;
-номер столбца: C = V mod M;
-если C<M:
то Matrix[V][V+1] = Matrix[V+1][V]=1;
- если R<M:
то Matrix[V][V+M] = Matrix[V+M][V]=1.
Здесь V – индекс (номер) вершины, знак «\» - целочисленное деление, «mod» - остаток от деления, Matrix – результирующая матрица смежности невзвешенного неориентированного графа.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
Рисунок 1 – Пример графа вида «правильная квадратная решетка»
размера 3 на 3
Пример создания правильной треугольной решетки
Псевдокод алгоритма заполнения матрицы смежности графа вида
«правильная треугольная решетка размера M на M»:
1)Создать нулевую квадратную матрицу Matrix размера M2 на M2;
2)Для каждой вершины V:
-номер строки: R = V \ M;
-номер столбца: C = V mod M;
-если C<M:
то Matrix[V][V+1] = Matrix[V+1][V]=1;
- если R<M:
то Matrix[V][V+M] = Matrix[V+M][V]=1.
- (если R mod 2 = 0 и C mod 2 = 0)
или (если R mod 2 = 1 и C mod 2 = 1):
то:
- если C>0:
то Matrix[V][V+M-1] = Matrix[V+M-1][V]=1; - если C<M:
то Matrix[V][V+M+1] = Matrix[V+M+1][V]=1;
Здесь V – индекс (номер) вершины, знак «\» - целочисленное деление, «mod» - остаток от деления, Matrix – результирующая матрица смежности невзвешенного неориентированного графа.
0 |
1 |
4 |
5 |
2 |
3 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
Рисунок 2 – Пример графа вида «правильная треугольная решетка»
размера 4 на 4
Пример создания правильной шестиугольной решетки
Псевдокод алгоритма заполнения матрицы смежности графа вида
«правильная шестиугольная решетка размера M на M»:
1)Создать нулевую квадратную матрицу Matrix размера M2 на M2;
2)Для каждой вершины V:
-номер строки: R = V \ M;
-номер столбца: C = V mod M;
-(если R mod 4 = 0 и C mod 2 = 1)
или (если R mod 4 = 2 и C mod 2 = 0):
то:
-если R>0:
то Matrix[V][V-M] = Matrix[V-M][V]=1; - если R<M и C<M:
то Matrix[V][V+M+1] = Matrix[V+M+1][V]=1; - если R<M и C>0:
то Matrix[V][V+M-1] = Matrix[V+M-1][V]=1;
3)Удаление лишних вершин:
-Пока массив суммы по строкам матрицы содержит значения меньше 2:
то удалить строку и столбец, где сумма по строке <2.
Здесь V – индекс (номер) вершины, знак «\» - целочисленное деление, «mod» - остаток от деления, Matrix – результирующая матрица смежности невзвешенного неориентированного графа.
0 |
1 |
2 |
6 |
7 |
8 |
12 |
13 |
14 |
3 |
4 |
5 |
9 |
10 |
11 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
30 |
31 |
26 |
27 |
32 |
33 |
28 |
29 |
34 |
35 |
Рисунок 3 – Пример графа вида «правильная шестиугольная решетка» размера 6 на 6
(серые узлы и ребра удаляются)