Реализация алгоритма Прима-Краскала на Python
В данной статье я расскажу о своем опыте создания программы на языке Python, которая реализует алгоритм Прима-Краскала․ Этот алгоритм позволяет найти кратчайшее остовное дерево во взвешенном неориентированном графе․ Исходный граф задается в виде матрицы смежности, которую мы вводим построчно через консоль․ Программа выводит список ребер, входящих в кратчайшее остовное дерево․
Шаги реализации
1․ Ввод матрицы смежности
Программа начинается с запроса ввода количества вершин графа․ Затем мы инициализируем двумерный массив матрицы смежности размером n x n, где n ⎼ количество вершин․ Далее мы последовательно заполняем матрицу, вводя значения ребер через консоль․Пример ввода матрицы смежности для графа с 4 вершинами⁚
0 2 0 6
2 0 3 8
0 3 0 0
6 8 0 0
2․ Инициализация остовного дерева
Мы создаем пустой список, который будет хранить ребра из кратчайшего остовного дерева․ Затем мы создаем список visited, в котором отслеживаем посещенные вершины․ Изначально все вершины помечаются как не посещенные․3․ Выбор вершины и добавление ребра
Мы начинаем с любой вершины графа и помечаем ее как посещенную․ Затем мы выбираем ребро с минимальным весом, которое связано с посещенными и непосещенными вершинами․ Добавляем это ребро в остовное дерево и помечаем новую вершину как посещенную․4․ Повторяем шаг 3, пока не посетим все вершины
Мы продолжаем выбирать ребра с минимальным весом, добавляя их в остовное дерево, пока не посетим все вершины графа․По окончании алгоритма, программа выводит список ребер, входящих в кратчайшее остовное дерево․
Пример работы программы
Давайте рассмотрим пример ввода матрицы смежности для графа с 4 вершинами⁚
0 2 0 6
2 0 3 8
0 3 0 0
6 8 0 0
Результат работы программы будет следующим⁚
Кратчайшее остовное дерево⁚
1 ⎼ 2⁚ 2
1 ⎼ 3⁚ 3
2 — 4⁚ 6
В этой статье я рассказал о своем опыте создания программы на языке Python, реализующей алгоритм Прима-Краскала․ Мы успешно нашли кратчайшее остовное дерево в заданном графе, используя матрицу смежности и консольный ввод․ По окончании работы программа вывела список ребер, входящих в остовное дерево․ Этот алгоритм может быть полезен в различных областях, где требуется оптимальное распределение ресурсов или построение минимальных связей․