Алгоритмы C++

Нахождение максимального остова

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

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

Дан взвешенный неориентированный граф. Требуется найти такое поддерево этого графа, которое бы соединяло все его вершины, и при этом обладало наименьшим весом (т.е. суммой весов рёбер) из всех возможных. Такое поддерево называется минимальным остовным деревом или простом минимальным остовом.

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

Свойства минимального остова

●Минимальный остов уникален, если веса всех рёбер различны. В противном случае, может существовать несколько минимальных остовов (конкретные алгоритмы обычно получают один из возможных остовов).

●Минимальный остов является также и остовом с минимальным произведением весов рёбер. (доказывается это легко, достаточно заменить веса всех рёбер на их логарифмы)

●Минимальный остов является также и остовом с минимальным весом самого тяжелого ребра. (это утверждение следует из справедливости алгоритма Крускала)

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

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

Данный алгоритм был описан Крускалом (Kruskal) в 1956 г.

Алгоритм Крускала изначально помещает каждую вершину в своё дерево, а затем постепенно объединяет эти деревья, объединяя на каждой итерации два некоторых дерева некоторым ребром. Перед началом выполнения алгоритма, все рёбра сортируются по весу (в порядке неубывания). Затем начинается процесс

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

Простейшая реализация

Этот код самым непосредственным образом реализует описанный выше алгоритм, и выполняется за O (M log N + N2). Сортировка рёбер потребует O (M log N) операций. Принадлежность вершины тому или иному поддереву

хранится просто с помощью массива tree_id - в нём для каждой вершины хранится номер дерева, которому она принадлежит. Для каждого ребра мы за O (1) определяем, принадлежат ли его концы разным деревьям.

Наконец, объединение двух деревьев осуществляется за O (N) простым проходом по массиву tree_id. Учитывая, что всего операций объединения будет N-1, мы и получаем асимптотику O (M log N + N2).

int m;

vector < pair < int, pair<int,int> > > g (m); // вес - вершина 1 - вершина 2

int cost = 0;

vector < pair<int,int> > res;

sort (g.begin(), g.end()); vector<int> tree_id (n); for (int i=0; i<n; ++i)

tree_id[i] = i; for (int i=0; i<m; ++i)

{

int a = g[i].second.first, b = g[i].second.second, l = g[i].first; if (tree_id[a] != tree_id[b])

{

cost += l;

res.push_back (make_pair (a, b));

int old_id = tree_id[b], new_id = tree_id[a]; for (int j=0; j<n; ++j)

if (tree_id[j] == old_id) tree_id[j] = new_id;

}

}

Улучшенная реализация

С использованием структуры данных "Система непересекающихся множеств" можно написать более быструю реализацию алгоритма Крускала с асимптотикой O (M log N).

Минимальное остовное дерево. Алгоритм Крускала с системой непересекающихся множеств

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

Здесь будет рассмотрена реализация с использованием структуры данных "система непересекающихся множеств" (DSU), которая позволит достигнуть асимптотики O (M log N).

Описание

Так же, как и в простой версии алгоритма Крускала, отсортируем все рёбра по неубыванию веса. Затем поместим каждую вершину в своё дерево (т.е. своё множество) с помощью вызова функции DSU MakeSet - на это уйдёт в сумме O (N). Перебираем все рёбра (в порядке сортировки) и для каждого ребра за O (1) определяем, принадлежат ли его концы разным деревьям (с помощью двух вызовов FindSet за O (1)). Наконец, объединение двух деревьев

будет осуществляться вызовом Union - также за O (1). Итого мы получаем асимптотику O (M log N + N + M) = O (M log N).

Реализация

Для уменьшения объёма кода реализуем все операции не в виде отдельных функций, а прямо в коде алгоритма Крускала. Здесь будет использоваться рандомизированная версия DSU.

vector<int> p (n);

int dsu_get (int v) {

return (v == p[v]) ? v : (p[v] = dsu_get (p[v]));

}

void dsu_unite (int a, int b) { a = dsu_get (a);

b = dsu_get (b); if (rand() & 1)

swap (a, b); if (a != b)

p[a] = b;

}

... в функции main(): ...

int m;

vector < pair < int, pair<int,int> > > g; // вес - вершина 1 - вершина 2

... чтение графа ...

int cost = 0;

vector < pair<int,int> > res;

sort (g.begin(), g.end()); p.resize (n);

for (int i=0; i<n; ++i) p[i] = i;

for (int i=0; i<m; ++i) {

int a = g[i].second.first, b = g[i].second.second, l = g[i].first; if (dsu_get(a) != dsu_get(b)) {

cost += l;

res.push_back (g[i].second); dsu_unite (a, b);

}

}

Матричная теорема Кирхгофа. Нахождение количества остовных деревьев

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

Приведённая ниже формула принадлежит Кирхгофу (Kirchhoff), который доказал её в 1847 г.

Матричная теорема Кирхгофа

Возьмём матрицу смежности графа G, заменим каждый элемент этой матрицы на противоположный, а на диагонале вместо элемента Ai,i поставим степень вершины i (если имеются кратные рёбра, то в степени вершины

они учитываются со своей кратностью). Тогда, согласно матричной теореме Кирхгофа, все алгебраические дополнения этой матрицы равны между собой, и равны количеству остовных деревьев этого графа. Например, можно удалить последнюю строку и последний столбец этой матрицы, и модуль её определителя будет равен искомому количеству.

Определитель матрицы можно найти за O (N3) с помощью метода Гаусса или метода Краута.

Доказательство этой теоремы достаточно сложно и здесь не приводится (см., например, Приезжев В.Б. "Задача о димерах и теорема Кирхгофа").

Связь с законами Кирхгофа в электрической цепи

Между матричной теоремой Кирхгофа и законами Кирхгофа для электрической цепи имеется удивительная связь. Можно показать (как следствие из закона Ома и первого закона Кирхгофа), что сопротивление Rij между точками i и j электрической цепи равно:

Rij = |T(i,j)| / |Tj|

где матрица T получена из матрицы A обратных сопротивлений проводников (Aij - обратное число к сопротивлению проводника между точками i и j) преобразованием, описанным в матричной теореме Кирхгофа,

а обозначение T(i) обозначает вычёркивание строки и столбца с номером i, а T(i,j) - вычёркивание двух строк и столбцов i и j. Теорема Кирхгофа придаёт этой формуле геометрический смысл.

Нахождение отрицательного цикла

Для решения этой задачи мы воспользуемся алгоритмом Форда-Беллмана, т.е. эту задачу мы решим за O (N M).

Известно, что алгоритм Форда-Беллмана в "чистом" виде некорректно работает на графе с отрицательным циклом. Тем не менее, результатом работы этого алгоритма можно воспользоваться для нахождения этого отрицательного цикла.

Алгоритм

Выполняем все N-1 итерации алгоритма Форда-Беллмана, сохраняя дополнительно массив предков. Затем дополнительно выполняем ещё одну итерацию. Если на ней оказывается, что какое-то значение массива D было улучшено в некоторой вершине X, то в графе имеется отрицательный цикл, иначе отрицательного цикла нет. Далее, чтобы найти сам цикл, пройдёмся по массиву предков от вершины X до тех пор, пока не зациклимся - этот цикл и будет искомым отрицательным циклом (следует заметить, что сама вершина X далеко не всегда входит в этот цикл).

Код

typedef pair<int,int> rib; typedef vector<rib> graf_line;

typedef graf_line::iterator graf_iter; typedef vector<graf_line> graf;

const int inf = 1000*1000*1000;

int main()

{

int n; graf g;

... чтение графа ...

vector<long long> d (n, inf); d[0] = 0;

vector<int> from (n, -1);

from[0] = 0; bool anychanged; int firstchanged;

for (int count=1; count<=n; count++)

{

anychanged = false; for (int v=0; v<n; v++)

if (d[v] < inf)

for (graf_iter i=g[v].begin(); i!=g[v].end();

++i)

{

int to = i->first, l = i->second; if (d[to] > d[v]+l)

{

d[to] = d[v]+l; from[to] = v;

if (!anychanged)

{

anychanged = true; firstchanged = to;

}

}

}

}

if (!anychanged) puts ("NO");

else

{

puts ("YES");

vector<int> path; path.reserve (n+1);

path.push_back (firstchanged); vector<char> used (n); used[firstchanged] = true;

int last = firstchanged;

for (int cur=from[firstchanged]; !used[cur]; last=cur=from[cur])

{

path.push_back (cur); used[cur] = true;

}

path.push_back (last);

path.erase (path.begin(), find (path.begin(), path.end

(), last));

reverse (path.begin(), path.end());

printf ("%d\n", (int)path.size()); for (size_t i=0; i<path.size(); i++)

printf ("%d ", path[i]+1);

}

}