Задача Прима-Краскала
Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной. В декартовой системе координат положение \(i\)-го города, \(i = 1,...,n\), задано парой координат \((x[i],y[i])\). \(d[i,j]\) - декартово расстояние между i-ым городом и j-ым городом , \(j=1,...,n\). В задаче речь идет о телефонной связи, т. е. подразумевается транзитивность связи: если i-й город связан с j-ым, а j-ый с k-ым, то i-й связан с k-ым.
Источник: http://pkgn.ru/do/TRPP/TrppKurs.pdf Алгоритм Краскала
