Минимальное остовное дерево с использованием алгоритма Крускала

Я использую алгоритм Крускала для выполнения задания по определению минимального остовного дерева следующей задачи:

У меня есть города, которые все должны быть связаны. Я могу соединить их, проложив между ними дороги или построив аэропорт. Когда я строю аэропорт в городе, он соединяется со всеми другими городами, в которых есть аэропорты.

Я сомневаюсь в следующем требовании:

В случае более чем одного оптимального решения я должен выбрать то, в котором меньше аэропортов. Как я могу гарантировать это наиболее эффективным способом?


algorithm minimum-spanning-tree kruskals-algorithm
person Rui Loureiro    schedule 30.04.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

В алгоритме Крускала мы сортируем и выбираем ребра в порядке неубывания их весов.

Допустим, мы используем структуру данных (что-то вроде кортежа) для хранения ребер как <source vertex,destination vertex, weight of edge between them>. Сортируем и выбираем ребра в порядке неубывания их веса.

Теперь в случае более чем одного оптимального решения вы предпочитаете то, в котором меньше аэропортов. Поэтому добавьте еще одно поле (скажем, типа boolean) в структуру данных для хранения, если в конечной вершине (городе) есть аэропорт. Это должно выглядеть примерно так: <source vertex,destination vertex, weight of edge between them, has_destination_an_airport>. has_destination_an_airport равен true, если в конечной вершине (городе) есть аэропорт, иначе false.

Теперь, когда мы сортируем ребра в порядке неубывания их весов, если веса одинаковы, то предпочитаем тот, у которого нет аэропорта, т.е. has_destination_an_airport это false, если возможно.

Подводя итог, можно сказать, что правильная реализация comparator для сортировки ребер сотворит чудо.

Что касается асимптотической временной и пространственной сложности, то она такая же, как и у алгоритма Крускала. Единственным накладным расходом является дополнительное поле, чтобы помнить, есть ли в конечной вершине аэропорт, что тривиально.

person Shridhar R Kulkarni    schedule 30.04.2017
comment
Спасибо, это очень простое и эффективное решение, именно то, что я искал. - person Rui Loureiro; 01.05.2017
comment
@RuiLoureiro: Рад помочь! Если вы считаете, что мой ответ был именно тем, что вы искали, отметьте его как принятый. - person Shridhar R Kulkarni; 01.05.2017