Задача 7. В стране Лимонии есть N городов, которые нужно соединить линиями связи.
Между какими городами нужно проложить линии связи, чтобы все города были связаны в одну
систему и общая длина линий связи была наименьшей?
В теории графов эта задача называется задачей построения минимального остовного дерева (то есть дерева, связывающего все вершины). Остовное дерево для связного графа с N вершинами имеем N-1 ребро.
Рассмотрим жадный алгоритм решения этой задачи, предложенный Крускалом:
1) начальное дерево – пустое;
2) на каждом шаге к будущему дереву добавляется ребро минимального веса, которое ещё не
было выбрано и не приводит к появлению цикла.
На рисунке показано минимальное остовное дерево для одного из рассмотренных выше графов
(сплошные жирные линии): (прикрепленно изображение)
Здесь возможна такая последовательность добавления рёбер: CE, DF, AB, EF, AC. Обратите внимание, что после добавления ребра EF следующее «свободное» ребро минимального веса – это DE
(длина 3), но оно образует цикл с рёбрами DF и EF, и поэтому не было включено в дерево.
При программировании этого алгоритма сразу возникает вопрос: как определить, что ребро
еще не включено в дерево и не образует цикла в нём? Существует очень красивое решение этой
проблемы, основанное на раскраске вершин.
Сначала все вершины раскрашиваются в разные цвета, то есть все рёбра из графа удаляются. Таким образом, мы получаем множество элементарных деревьев (так называемый лес), каждое из которых состоит из одной вершины. Затем последовательно соединяем отдельные деревья, каждый раз выбирая ребро минимальной длины, соединяющее разные деревья (выкрашенные в разные цвета). Объединённое дерево перекрашивается в один цвет, совпадающий с цветом
одного из вошедших в него поддеревьев. В конце концов все вершины оказываются выкрашены в
один цвет, то есть все они принадлежат одному остовному дереву. Можно доказать, что это дерево будет иметь минимальный вес, если на каждом шаге выбирать подходящее ребро минимальной длины.
В программе сначала присвоим всем вершинам разные числовые коды:
col =
Здесь N – количество вершин, а col – «цвета» вершин (список из N элементов).
Затем в цикле N-1 раз (именно столько рёбер нужно включить в дерево) выполняем следующие операции:
1) ищем ребро минимальной длины среди всех рёбер, концы которых окрашены в разные
цвета;
2) найденное ребро в виде кортежа(iMin,jMin) добавляется в список выбранных, и все
вершины, имеющие цвет col, перекрашиваются в цвет col.
Приведем полностью основной цикл программы:
ostov =
for k in range(N-1):
# поиск ребра с минимальным весом
minDist = 1e10 # очень большое число
for i in range(N):
for j in range(N):
if col != col and W < minDist:
iMin = i
jMin = j
minDist = W
# добавление ребра в список выбранных
ostov.append ( (iMin, jMin) )
# перекрашивание вершин
c = col
for i in range(N):
if col == c:
col = col
Здесь W – весовая матрица размера N на N (индексы строк и столбцов начинаются с 0); ostov –
список хранения выбранных рёбер (для каждого ребра хранится кортеж из номеров двух вершин,
которые оно соединяет). Если связи между вершинами i и j нет, в элементе W матрицы
будем хранить «бесконечность» – число, намного большее, чем длина любого ребра. При этом
начальное значение переменной minDist должно быть ещё больше.
После окончания цикла остается вывести результат – рёбра из массива ostov:
for edge in ostov:
print ( “(”, edge, “,”, edge, “)” )
В цикле перебираются все элементы списка ostov; каждый из них – кортеж из двух элементов –
попадает в переменную edge, так что номера вершин определяются как edge и edge.
ПОМОГИТЕ ПОЖАЛУЙСТА! НАДО СДАТЬ РАБОТУ, НАПИСАТЬ ПРОГРАММУ ПО ДАННОЙ ЗАДАЧЕ! ПРОШУ ПОМОЩИ!