Python-сообщество

Тема 24: Задача Прима-Краскала (жадный алгоритм) - L
Дана плоская страна и в ней n городов. Нужно соединить все города телефонной
связью так, чтобы общая длина телефонных линий была минимальной. Уточнение задачи. В декартовой системе координат положение i-го города, i = 1,…,n, задано парой координат (x,y). d - декартово расстояние между i-ым городом и j-ым
городом , j=1,…,n. В задаче речь идет о телефонной связи, т. е. подразумевается
транзитивность связи: если i-й город связан с j-ым, а j-ый с k-ым, то i-й связан с k-ым. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. В терминах теории графов задача Прима-Краскала выглядит следующим образом:
Дан граф с n вершинами; длины ребер заданы матрицей (d), i,j = 1,…,n. Найти остовное дерево минимальной длины. Как известно, дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро надо выбирать жадно (лишь бы ни возникали циклы).
Алгоритм Прима-Краскала
(краткое описание)
В цикле n-1 раз делай:
выбрать самое короткое еще не выбранное ребро при условии, что оно не образует цикл с уже выбранными.
Выбранные таким образом ребра образуют искомое остовное дерево.
Напишите программу для решения задачи Прима-Краскала.