Алгоритмы[править | править вики-текст]

Простейший алгоритм решения задачи о поиске сильно связных компонент в орграфе работает следующим образом:

1. При помощи транзитивного замыкания проверяем, достижима ли t из s, и s из t, для всех пар s и t.

2. Затем определяем такой неориентированный граф, в котором для каждой такой пары содержится ребро.

3. Поиск компонент связности такого неориентированного графа даст нам компоненты сильной связности нашего орграфа.

Очевидно основное время работы данного алгоритма приходится на реализацию транзитивного замыкания.

Также существует три алгоритма, решающих данную задачу за линейное время, то есть в V раз быстрее, чем приведенный выше алгоритм. Это алгоритмыКосарайю, Габова и Тарьяна.

    Граф компонентов (конденсация графа)

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

3. Минимальные остовные деревья (мst)

    Определение

    Общая схема построения

    Безопасные ребра 

Введение

В статье рассматривается задача о построении минимального остовного дерева (minimum-spanning-tree problem). В начале статьи дано общее описание проблемы и история подходов к ее решению. Далее описан базовый алгоритм и некоторые теоретические сведения о минимальных остовных деревьях. В конце статьи представлены основные алгоритмы (Крускал, Прим, Борувка).

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

Итак, имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна?

В общем случае, задачу можно сформулировать так. Пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V — множество вершин (контактов), аE — множество их возможных попарных соединений (ребер). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или стоимость соединения). w() называется весовой функцией. Задача состоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.

Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом (spanning tree). Остовное дерево T, у которого суммарный вес его ребер w(T) = ∑_(u,v)∈T w(u,v) минимален, называется минимальным остовным или минимальным покрывающим деревом (minimum spanning tree).

Рис. 1. Минимальное остовное дерево. Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.

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

Рис.2-а. Минимальное остовное дерево. Суммарный вес равен 3.	Рис.2-б. Минимальный покрывающий подграф. Суммарный вес равен 0.

Также считаем, что для любой пары ребер их весовые характеристики будут различны. Это гарантирует уникальность построенного минимального остовного дерева. Для примера, если все ребра имеют единичный вес, то любое остовное дерево будет минимальным (с суммарным весом v-1, где v – количество вершин в графе).

Рис.3. Все возможные минимальные остовные деревья для данного графа.

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

SHORTER-EDGE(i;j;k;l) 1: if w(i,j) < w(k,l) then return (i,j) 2: if w(i,j) > w(k,l) then return (k,l) 3: if min(i,j) < min(k,l) then return (i,j) 4: if min(i,j) > min(k,l) then return (k,l) 5: if max(i,j) < max(k,l) then return (i,j) 6: return (k,l)

    Теорема о легком ребре, пересекающем разрез, согласованный по ребрам с текущим подмножеством MST 

    Алгоритм Прима (время работы с кучей и с массивом, для каких графов что эффективнее)

При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получает на вход граф G и его корень r – вершина, на которой будет наращиваться минимальный остов. Все вершины G, еще не попавшие в дерево, хранятся в очереди с приоритетом Ω. Приоритет вершины v определяется значением key[v], которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле p[v] для вершин дерева указывает на родителя, а для вершин из очереди, указывает на ноду дерева, в которою ведет ребро с весом key[v] (одно из таких ребер, если их несколько).

Тогда алгоритм Прима выглядит следующим образом:

MST-PRIM(G,w, r) 1: Ω ← V[G] 2: foreach (для каждой) вершины u ∈ Ω 3:     do key[u] ← ∞ 4: key[r] ← 0 5: p[r] = NIL 6: while (пока) Ω ≠ 0 7:     do u ← EXTRACT-MIN(Ω) 8:        foreach (для каждой) вершины v ∈ Adj(u) 9:            do if v ∈ Ω и w(u,v) < key[v] then 10:               p[v] ← u 11:               key[v] ← w(u,v)

На рисунках П1-П8 показана схема работы алгоритма Прима с корнем r.

Рис. П1. Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер.	Рис. П2. Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.
Рис. П3. Следующее безопасное ребро с весом 11. Добавляем его.	Рис. П4.
Рис. П5.	Рис. П6.
Рис. П7.	Рис. П8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Время работы алгоритма Прима зависит от того, как реализована очередь с приоритетами Ω. Если использовать двоичную кучу, инициализацию в строках 1-4 можно выполнить за время O(V). Далее цикл выполняется |V| раз, и каждая операция EXTRACT-MIN занимает время O(VlogV). Цикл for в строках 8-11 выполняется в общей сложности O(E), поскольку сумма степеней вершин графа равна 2|E|. Проверку принадлежности в строке 9 можно выполнить за время O(1), если хранить состояние очереди еще и как битовый вектор размера |V|. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (DECREASE-KEY), которая для двоичной кучи может быть выполнена за время O(logV). Таким образом всего получаем O(VlogV+ElogV)=O(ElogV).

Лучшую оценку можно получить, если использовать фибоначчиевы кучи. С помощью фибоначчиевых куч можно выполнить операцию EXTRACT-MIN за учетное время O(logV), а операцию DECREASE-KEY – за учетное время O(1). В этом случае суммарное время работы алгоритма Прима составит O(E+VlogV).