ГУАП
КАФЕДРА № 41
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
ассистент |
|
|
|
М.Н. Шелест |
|
|
|
|
|
|
|
|
|
|
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №2
БАЗОВЫЕ АЛГОРИТМЫ НА ГРАФАХ
по курсу: ПОСТРОЕНИЕ И АНАЛИЗ ГРАФОВЫХ МОДЕЛЕЙ
РАБОТУ ВЫПОЛНИЛ СТУДЕНТ ГР. №
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург 2022
Цель работы
Реализовать и проверить на тестовом примере базовый алгоритм на графе. Сравнить быстродействие реализованного алгоритма на специальных графах.
Индивидуальный вариант
Задание согласно индивидуальному варианту №10 в соответствии с таблицей 1.
Таблица 1 – Задание индивидуального варианта
№ варианта
Наименование
(алгоритма/ типа графа)
2 |
Алгоритм поиска минимального остовного |
|
дерева (алгоритм Прима) |
||
|
||
|
|
|
2 |
Правильная треугольная решетка |
2
Ход работы
1) Написали подпрограмму, реализующую отображение графа на экране. Функция view_graph для отображения графа на экране. Список использованных переменных в соответствии с таблицей 2, код в соответствии с листингом 1. Результат работы функций в соответствии с рисунком 1.
Таблица 2 – Список переменных подпрограммы из Листинга 1
Название |
Значение |
|
|
adj_mat |
Матрица смежности |
|
|
peaks |
Список вершин |
|
|
curved_value |
Тип отображения связей (прямые или округлие) |
|
|
g |
Объект графа |
|
|
list_edges |
Список ребер |
|
|
weights |
Список весов ребер |
|
|
Листинг 1 – Подпрограмма отображения графа на экране
def view_graph(adj_mat, peaks = [], curved_value = False): if not peaks: peaks = list(adj_mat)
g |
= ig.Graph() |
# создание ориентированного графа |
|
g.add_vertices(len(peaks)) |
# добавление вершин графа |
||
# |
добавление идентификаторов и меток к вершинам |
for i in range(len(g.vs)):
g.vs[i]["id"]= peaks[i] if isinstance(peaks[i], int)
else i
g.vs[i]["label"]= peaks[i]
# получаем список ребер и их веса
list_edges = [(row, col) for col in range(len(adj_mat)) for row in range(len(adj_mat)) if adj_mat[row][col]]
# задаем ребра g.add_edges(list_edges)
# задаем веса ребер
weights = [adj_mat[row][col] for col in range(len(adj_mat)) for row in range(len(adj_mat)) if adj_mat[row][col]]
g.es['label'] = weights |
|
g.es['edge_width'] = weights |
|
g.es["curved"] = curved_value |
# кривизна ребер |
ig.plot(g, bbox = (500, 500) |
# построение графика |
, margin = 30 |
|
, vertex_color = 'white') |
|
return 1 |
|
3
Рисунок 1 – Результат работы функции
4
2) Самостоятельно составили и визуализировали взвешенный граф в представлении матрицы смежности. Матрица смежности в соответствии с рисунком 2, граф правильной треугольной решетки в соответствии с рисунком 3.
Рисунок 2 – Матрица смежности
Рисунок 3 – Граф правильной треугольной решетки
3)Базовый алгоритм поиска минимального остовного дерева
(алгоритм Прима).
Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.
На вход алгоритма подаётся связный неориентированный граф. Для каждого ребра задаётся его стоимость.
Сначала берётся произвольная вершина и находится ребро, инцидентное
5
данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой
— нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.
Результатом работы алгоритма является остовное дерево минимальной стоимости.
4)Применение «на бумаге» заданного алгоритма для графа,
созданного в пункте 1 порядка выполнения п/р.
Исходный граф в соответствии с рисунком 4.
Рисунок 4 – Граф правильной треугольной решетки Выбираем случайным образом первую вершину. Начнем с вершины 2 в
соответствии с рисунком 5.
Рисунок 5 – Алгоритм Прима этап 1
Затем находим ребро инцидентное данной вершине с наименьшим весом и добавляем его в остовное дерево в соответствии с рисунком 6.
6
Рисунок 6 – Алгоритм Прима этап 2
Затем из оставшихся выбираем ребро наименьшего веса, один конец которого уже присутствует в остовном дереве, а второй нет в соответствии с рисунком 7.
Рисунок 7 – Алгоритм Прима этап 3
7
Аналогично предыдущему пункты повторяем выбор ребер пока все вершины не окажутся включены в остовное дерево в соответствии с рисунками 8-13.
Рисунок 8 – Алгоритм |
Рисунок 9 – Алгоритм |
Рисунок 10 – Алгоритм |
Прима этап 4 |
Прима этап 5 |
Прима этап 6 |
Рисунок 11 – Алгоритм |
Рисунок 12 – Алгоритм |
Рисунок 13 – Алгоритм |
Прима этап 7 |
Прима этап 8 |
Прима этап 9 |
Итоговое остовное дерево в соответствии с рисунком 12.
8
5) Написали подпрограмму, реализующую создание остовного дерева графа по матрице смежности.
Функции algoritm_prima и search_min для построения остовного дерева.
Список использованных переменных в соответствии с таблицами 3-4, код в соответствии с листингами 2-3. Результат работы функций в соответствии с рисунком 14.
Таблица 3 – Список переменных подпрограммы из Листинга 2
Название |
Значение |
|
|
adj_mat |
Матрица смежности |
|
|
size |
Размер стороны графа (кол-во вершин в ней) |
|
|
vizited |
Словарь посещенных вершин |
|
|
result |
Список ребер остовного дерева |
|
|
edge |
Ребро графа, которое следующим нужно добавить в остовное |
|
дерево |
|
|
Листинг 2 – Подпрограмма построения остовного дерева алгоритм Прима
def algoritm_prima(adj_mat): |
|
|
|
size = len(adj_mat) |
# число вершин в графе |
||
vizited = {rd.choice([i for i in range(size)])} |
# множество |
||
соединенных вершин |
|
|
|
result = [] |
# список ребер остова |
||
while len(vizited) < size: |
|
|
|
edge = search_min(adj_mat, |
vizited) |
# ребро с |
|
минимальным весом |
|
|
|
if edge[2] == math.inf: |
|
# если ребер нет, то |
|
остов построен |
|
|
|
return False |
|
|
|
result.extend([edge[0], edge[1]]) |
# добавляем ребро в |
||
остов |
|
|
|
vizited.add(edge[0][0]) |
|
# добавляем вершины |
в множество vizited.add(edge[0][1])
return pd.DataFrame([[adj_mat[row][col] if (row, col) in result else 0 for col in range(size)] for row in range(size)])
9
Таблица 4 – Список переменных подпрограммы из Листинга 3
Название |
Значение |
|
|
adj_mat |
Матрица смежности |
|
|
vizited |
Словарь посещенных вершин |
|
|
min_v |
Ребро минимального веса, одна из вершин которого в остовном |
|
дереве |
|
|
row |
Итератор по номерам посещенных вершин |
|
|
col |
Итератор по номерам связей для посещенных вершин |
|
|
elem |
Итератор по весам связей для посещенных вершин |
|
|
Листинг 3 – Подпрограмма нахождения ребра с минимальным весом для алгоритма Прима
def search_min(adj_mat, vizited): min_v = (-1, -1, math.inf) for row in vizited:
for col, elem in enumerate(adj_mat[row]):
if col not in vizited and elem != 0 and elem <
min_v[2]:
min_v = (row, col, elem)
return [(min_v[0], min_v[1]), (min_v[1], min_v[0]), elem]
6) Выполнили отладку работы алгоритма на графе, созданном по пункту 1 порядка выполнения практической работы. Результат работы алгоритма в соответствии с рисунком 15.
Рисунок 14 – Остовное дерево граф правильной треугольной решетки
10