Раздел «Алгоритмы».MinimalCoveringTree:

Минимальное покрывающее дерево

Постановка задачи

Дан связный неориентированный граф с взвешенными ребрами. Вес ребер соответствует длине. Нужно удалить ребра как можно большей суммарной длины оставив граф связным. Понятно, что в должно получиться дерево, множество вершин которого совпадает с множеством вершин исходного графа, а ребра — подмножество рёбер исходного графа.

Идея решения

Основная идея — жадность. Есть два основных алгоритма, решающих эту задачу.

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

Для начала упорядочим ребра, потратив на это время  E \log E \le  V^2\log V^2 \approx V^2\log V , где  V есть число вершин, а E — число ребер.

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

Жадность заключается в том, что мы постоянно хотим добавлять самое кратчайшее из оставшихся ребер, если, конечно, добавление его имеет смысл.

В ходе работы алгоритма нам нужно хранить текущее разбиение вершин на компоненты, уметь определять по вершине, какой компоненте она принадлежит, а также уметь объединять две компоненты в одну. Добавить к каждой вершине аттрибут "идентификатор компоненты" --- не самое лучшее решение задачи, так как придется перекрашивать вершины одной из компонент при объединении двух компонент. Одно из "умных" решениний заключается в том, что каждая компонента хранится в памяти как корневое дерево с направленными ребрами, а при объединении компонент мы одно дерево "прививаем к другому", то есть проводим ребро от корня одного к корню другого дерева. Идентификатором компоненты служит корень дерева, к которому принадлежит вершины. Таким образом, чтобы узнать компоненту вершины, нужно добраться до корня дерева, а это займет столько времени, какова высота этого дерева. Высоту дерева можно поддерживать маленькой, просто после каждого прохода от вершины к корню на обратном пути пересаживать все вершины пути сразу к корню.

Алгоритм Прима

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

В каждый момент имеем дерево, частично покрывающее граф и ищем следующую вершину, ближайшую к этому дерева.

Необходимо на каждом шаге находить ближайшую вершину из отсавшихся. Для оптимизации поиска такой вершины, необходимо оставшиеся вершины хранить в очереди с приоритетом и извлекать ближайшую вершину с момощью операции extract_min. Ключом вершины будет расстояние до текущего дерева. После добавления извлечённой вершины к дереву, необходимо просмотреть её смежные вершины и, при необходимости, обновить их ключи.

Примеры кода

-- ArtemVoroztsov - 06 Apr 2004

AlgorithmClasifyForm
Type: Теория
Scope: Графы
Strategy: Жадность
Language:  
Complexity: Medium