Создание программы на Python, реализующей алгоритм Прима-Краскала
Привет, меня зовут Алексей, и я хочу поделиться с вами своим опытом создания программы на Python, которая реализует алгоритм Прима-Краскала. Этот алгоритм используется для построения кратчайшего остовного дерева в заданном взвешенном графе.
Для начала, давайте определимся с тем, что такое матрица смежности. Матрица смежности представляет собой квадратную матрицу, в которой строки и столбцы представляют вершины графа, а элементы матрицы указывают наличие или отсутствие ребер между вершинами. Если ребро есть, то элемент матрицы будет содержать вес этого ребра. Если ребра нет, то элемент матрицы будет содержать ноль или бесконечность (в зависимости от того, какую константу вы выберете для обозначения отсутствия ребра).
Теперь перейдем к созданию программы. Сначала нам нужно получить матрицу смежности от пользователя; Воспользуемся функцией input, чтобы пользователь мог вводить строки матрицы смежности по одной прямо в консоли. Чтобы упростить работу с матрицей, предлагаю использовать библиотеку NumPy⁚
import numpy as np
size int(input(″Введите размер матрицы смежности⁚ ″))
matrix np.zeros((size, size)) # Создаем матрицу с нулями
for i in range(size)⁚
row input(″Введите строку матрицы⁚ ″).split
for j in range(size)⁚
matrix[i][j] int(row[j])
Теперь мы имеем матрицу смежности. Следующим шагом я предлагаю реализовать сам алгоритм Прима-Краскала. Суть алгоритма заключается в выборе начальной вершины и последующем добавлении ребра с наименьшим весом, которое соединяет уже выбранные вершины с невыбранными. При этом мы должны следить за тем, чтобы не образовывался цикл.
# Находим ребра кратчайшего остовного дерева
minimum_spanning_tree []
selected_vertices set
selected_vertices.add(0)
while len(selected_vertices) < size⁚
min_weight float('inf')
u, v None, None
for i in selected_vertices⁚
for j in range(size)⁚
if j not in selected_vertices and matrix[i][j] ! 0 and matrix[i][j] < min_weight⁚
min_weight matrix[i][j]
u, v i, j
selected_vertices.add(v)
minimum_spanning_tree;append((u, v, min_weight))
Теперь, когда мы имеем список ребер кратчайшего остовного дерева, мы можем вывести его на экран. Воспользуемся циклом for, чтобы пройти по всем ребрам и вывести их⁚
print(″Список ребер кратчайшего остовного дерева⁚″)
for edge in minimum_spanning_tree⁚
print(f″{edge[0]} ⎼ {edge[1]}⁚ вес {edge[2]}″)
И вот мы закончили! Теперь у нас есть полностью рабочая программа на Python, которая реализует алгоритм Прима-Краскала для построения кратчайшего остовного дерева по заданной матрице смежности.
Надеюсь, мой опыт будет полезен и поможет вам в создании подобной программы!