Алгоритм Краскала

Введение

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

Алгоритм Краскала

Идея алгоритма Краскала состоит в построении основания, а именно остова дерева выбранного графа на минимальной величине. Рассмотрим конкретный пример. Есть карта, на которой отмечено некоторое количество городов, которые требуется связать между собой дорогами. При этом необходимо соблюсти условие, а именно общая длина дорог должна быть самой маленькой.

Статья: Алгоритм Краскала

Найди решение своей задачи среди 1 000 000 ответов

Найти решение задачи

Рисунок 1. Алгоритм Краскала. Автор24 — интернет-биржа студенческих работ

Чтобы решить эту задачу, необходимо иметь:

1. Требуемый набор графов.
2. Описание алгоритма Красала.
3. Disjoint-set data structure: дополняющая структура, которая требуется, чтобы эффективно выполнить данный алгоритм.

Рисунок 2. Алгоритм Краскала. Автор24 — интернет-биржа студенческих работ

В поставленной задаче в качестве вершин графа Vj, приняты города, а в качестве рёбер e(Vi, Vj), приняты соединяющие города дороги. В качестве исходного параметра, так же, присутствуют расстояния между двумя городами Vi, Vj, которые являются весами рёбер W(e(Vi, Vj)). Необходимо определить MST, то есть найти дерево в графе, не имеющее циклов (это избыточные дороги), чтобы суммарный вес рёбер был самым маленьким, а все вершины возможно было достичь.

Для работы алгоритма необходимо сформировать множество вершин G таким образом, чтобы входящие в него вершины входили в MST.

Для достижения этой цели надо:

1. Выполнить сортировку всех рёбер графа по увеличению их веса (то есть возрастанию длины дороги).

2. Выполняем обход рёбер графа по возрастанию их весов и анализируем конец ребра e = (a, b):

   • В случае принадлежности вершин a и b одному множеству, делаем вывод, что они уже принадлежат некоему образованному подмножеству малое MST. Там есть уже свой подграф с минимальной суммой рёбер. Это ребро алгоритм пропускает, поскольку в противном случае оно приведёт к образованию цикла в дереве.
   • В случае принадлежности вершин a и b различным подмножествам малого MST, значит их необходимо объединить, поскольку найдено ребро (дорога) с самой маленькой длиной, которое объединяет два подмножества в единое целое. Рёбра, обладающие меньшей длиной, алгоритм уже просмотрел, и объединить с меньшей стоимостью, чем текущая, вариантов не остаётся. Это ребро вносится в число рёбер, необходимых для формирования дерева MST, а множества сливаются в одно.
   • Алгоритм продолжает выполнение цикла объединения до тех пор, пока не получится единое множество, которое равняется требуемому MST и где присутствуют все вершины графа.

3. В итоге находим искомое множество вершин MST со списком рёбер, применяемых для его соединения. Это и есть дерево самого маленького суммарного веса, которое объединяет все вершины.

Рисунок 3. Алгоритм Краскала. Автор24 — интернет-биржа студенческих работ

Система непересекающихся множеств

Чтобы реализовать понятие множество при использовании алгоритма Краскала, возможно применить структуру данных, которая называется система непересекающихся множеств (Disjoint-set data structure). Использование этой структуры наиболее оптимально при реализации следующих операций:

1. Определить, к какому из множеств относится на данный момент заданная вершина.
2. Выполнить быстрое объединение этих множеств в единое целое.

Рассмотрим конкретный пример. Необходимо выполнить сегментацию изображения попугая на фоне морского побережья. Изначально каждая вершина графа (это пиксель, в нашем случае) отделена от других и находится в своём множестве (сегменте), но в процессе работы алгоритма вершины (пиксели) близкие по цвету (единого объекта) постепенно будут соединяться в одно множество (один сегмент). Предположим, на некотором шаге алгоритма обрабатывается ребро, которое соединяет пару соседних пикселей. С одного конца ребра пиксель оранжевого цвета, а с другого конца красный пиксель. Размер ребра можно рассматривать как разность цвета пикселей. Все другие рёбра, имеющие меньшую длину (с близкими цветами) уже соединены. Со стопроцентной вероятностью уже определены оранжевая и красная вершины (сегменты) попугая. Согласно алгоритму, необходимо определить, находятся в одном сегменте или нет оранжевый и красный пиксели. Если они в различных сегментах, и мы полагаем, что сегменты похожи по цветам, то выполняем их объединение и следуем дальше. Это, по сути, алгоритм Краскала, но работающий с пикселями. Применяемая для этих процедур структура аналогична дереву, но формируется массивом индексов. В этой структуре для каждого пикселя сохранена его история, то есть существует указатель (индексный) на некий похожий по расцветке пиксель, который находится в этом же сегменте.

Базовые операции следующие:

1. Процедура поиска сегмента некоего пикселя Х. Выполняется проход по его истории к самому истоку (верху). Верхний пиксель является корнем дерева, представляющем данный сегмент на текущий момент.
2. Соединение сегментов. Если пиксели имеют различных «представителей», то это означает их принадлежность к разным сегментам, так как в противном случае у них был бы один корень. Чтобы их объединить, надо «представителя» сегмента с меньшей высотой (от максимально удалённого пикселя от корня) отослать (указателем, который у него есть) на «представителя», который длиннее. При этом высота дерева не увеличивается. Получаем объединение сегментов с общим представителем.

Процесс может быть оптимизирован, если после обнаружения «представителя» установить прямую ссылку в пикселе непосредственно на этого представителя. Эта модификация существенно уменьшает маршруты последующих процессов поиска, и носит название сжатие пути (path compression).

Рисунок 4. Сжатие пути. Автор24 — интернет-биржа студенческих работ