ЛР / ЛР2 / ПиАГМ ЛР2

Цель работы

Реализовать и проверить на тестовом примере базовый алгоритм на графе. Сравнить быстродействие реализованного алгоритма на специальных графах.

Индивидуальный вариант

Задание согласно индивидуальному варианту №10 в соответствии с таблицей 1.

Таблица 1 – Задание индивидуального варианта

№ варианта

Наименование

(алгоритма/ типа графа)

2

Ход работы

1) Написали подпрограмму, реализующую отображение графа на экране. Функция view_graph для отображения графа на экране. Список использованных переменных в соответствии с таблицей 2, код в соответствии с листингом 1. Результат работы функций в соответствии с рисунком 1.

Таблица 2 – Список переменных подпрограммы из Листинга 1

Листинг 1 – Подпрограмма отображения графа на экране

def view_graph(adj_mat, peaks = [], curved_value = False): if not peaks: peaks = list(adj_mat)

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]]

3

Рисунок 1 – Результат работы функции

4

2) Самостоятельно составили и визуализировали взвешенный граф в представлении матрицы смежности. Матрица смежности в соответствии с рисунком 2, граф правильной треугольной решетки в соответствии с рисунком 3.

Рисунок 2 – Матрица смежности

Рисунок 3 – Граф правильной треугольной решетки

3)Базовый алгоритм поиска минимального остовного дерева

(алгоритм Прима).

Алгоритм Прима — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа.

На вход алгоритма подаётся связный неориентированный граф. Для каждого ребра задаётся его стоимость.

Сначала берётся произвольная вершина и находится ребро, инцидентное

5

данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой

— нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.

Результатом работы алгоритма является остовное дерево минимальной стоимости.

4)Применение «на бумаге» заданного алгоритма для графа,

созданного в пункте 1 порядка выполнения п/р.

Исходный граф в соответствии с рисунком 4.

Рисунок 4 – Граф правильной треугольной решетки Выбираем случайным образом первую вершину. Начнем с вершины 2 в

соответствии с рисунком 5.

Рисунок 5 – Алгоритм Прима этап 1

Затем находим ребро инцидентное данной вершине с наименьшим весом и добавляем его в остовное дерево в соответствии с рисунком 6.

6

Аналогично предыдущему пункты повторяем выбор ребер пока все вершины не окажутся включены в остовное дерево в соответствии с рисунками 8-13.

Итоговое остовное дерево в соответствии с рисунком 12.

8

5) Написали подпрограмму, реализующую создание остовного дерева графа по матрице смежности.

Функции algoritm_prima и search_min для построения остовного дерева.

Список использованных переменных в соответствии с таблицами 3-4, код в соответствии с листингами 2-3. Результат работы функций в соответствии с рисунком 14.

Таблица 3 – Список переменных подпрограммы из Листинга 2

Листинг 2 – Подпрограмма построения остовного дерева алгоритм Прима

в множество 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

Листинг 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