Классические задачи на графах Алгоритм (Крускалла) построения минимального остовного дерева.

26. Простейшая задача (1 условная задача) http://video.yandex.ru/users/o-krivosheev/view/302/# Жадный алгоритм (Крускалла) Построить минимальноеостовноедерево.

Указание ПРЕПОДАВАТЕЛЯМ – с этой задачи крайне рекомендуется начинать СЕМЕСТР.

Указание: Ответ должен содержать все шаги алгоритма (включаемые в сеть дорог отрезки) в правильной последовательности их выбора. В алгоритме построения минимального остовного дерева последовательно выбираются ребра (отрезки возможных путей) минимальные из оставшихся.

(Презентация ИССЛЕДОВАНЕ ОПЕРАЦИЙ).

Пример:

Алгоритм:

Адаптированный под бумажно-ручное решение алгоритм Крускалла:

1) выбираем самое короткое из ребер.

2) выбираем второе за ним (может быть равное предыдущему).

3) начиная с третьего ребра добавляем самые короткие рёбра из оставшихся, при условии, что они не порождают зацикливаний вместе с ранее выбранными рёбрами.

В любом остовном дереве должно быть n-1 ребро, что можно считать простейшим критерием остановки алгоритма. (Забывание этого критерия не приведёт к ошибке, т.к. все остальные ребра придётся последовательно запретить).

Разберём логику решения на простом примере с пошаговой эволюцией рисунка (при этом рисунок достаточно нарисовать один раз. Разрешенные ребра делать жирными, а запрещенные ребра отмечать s–образной волной).

Построить минимальное остовное дерево.

Шаг 1.

Вводим вершины минимальным весом 1.

Связаны не все пункты.

Вводим вершины минимальным весом из оставшихся 3.

Связаны не все пункты.

Вводим вершины минимальным весом из оставшихся 4.

Один пункт оторван, ищем дугу минимального веса, связывающей Ригу с сетью - 7.

Получили минимальное остовное дерево весом 1+1+3+4+7=16.