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

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

Пусть G = (V, E, W) - неориентированный граф без петель со взвешенными ребрами и пусть множество вершин V={1, …, n}, множество ребер E Í V´V, |E| = m и весовая функция W(u, v) каждому ребру (u, v)ÎE ставит в соответствие неотрицательное число - его вес.

Требуется найти минимальный остов графа, то есть минимальное по весу поддерево графа G, содержащее все его вершины.

Решением задачи будем считать массив ET[1..n-1, 1..2], в котором пара (ET[i, 1], ET[i, 2]) является i-м ребром построенного минимального остовного дерева.

Стратегии решения задачи

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

Стратегия 1(Boruvka).

Вначале все вершины окрашиваются в синий цвет, а все ребра остаются неокрашенными.

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

Стратегия 2(Kruskal).

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

Повторяющийся шаг: выбирается очередное неокрашенное ребро в порядке неубывания стоимости; если оба его конца принадлежат одному и тому же синему дереву, то ребро окрашивается в красный цвет, в противном случае – в синий.

Стратегия 3 (Prim).

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

Повторяющийся шаг:выбирается инцидентное синему дереву неокрашенное ребро минимальной стоимости; если оба его конца принадлежат одному и тому же синему дереву, то ребро окрашивается в красный цвет, в противном случае – в синий.

Стратегия 4 (Yao).

Вначале все вершины окрашиваются в синий цвет, а все ребра остаются неокрашенными.

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

В алгоритмах, реализующих данные стратегии, будем применять разделенные множества с использованием рангов и сжатия путей (см. [5]). Для коллекции K разделенных множеств будем использовать операции:

· Найти(i, j, K) - найти имя i подмножества коллекции K, содержащее элемент j;

· Объединить(i, j) - объединить подмножества коллекции с именами i и j.

Алгоритм Борувки

В данном алгоритме (см. [2]) используется представления исходного графа G массивом E[1..m] его ребер и массивом W[1..m] весов данных ребер.

procedure MSP_BORUVKA(var ET; var mt; G; n,m);

begin

for s:= 1 to n do NME[s]:= 0;

Создать коллекцию K из n синглетонов множества {1, 2, … , n};

mt:= 0;

while FIND_NME(NME,K,E,G,n,m) do for s:= 1 to n do if NME[s]>0 then begin

a=E[NME[s]][1]; b=E[NME[s]][2]; Найти(i, a, K); Найти(j, b, K);

if i ¹ j then begin mt:= mt+1; ET[mt]:= E[NME[s]]; Объединить(i,j,K); end;

NME[s]:= 0;

end;

end;

Функция FIND_NME осуществляет повторяющийся шаг стратегии Борувки: для каждого синего дерева, представленного в коллекции множеством своих вершин, которое имеет имя s, находит инцидентное ему неокрашенное ребро минимальной стоимости с наименьшим номером NME(s), концы которого не являются вершинами одного итого же синего дерева. При этом функция FIND_NME возвращает значение true, если хотя бы одно такое ребро найти удалось, и возвращает значение false, если этого сделать не получилось.

function FIND_NME(var NME; K; E; G; n,m) : boolean;

begin

FIND_NME = false;

for t:= 1 to m do begin

a=E[t][1]; b=E[t][2];

Найти(i,a,K); Найти(j,b,K);

if i¹j then begin

if NME[i]=0 then begin

NME[i]:= t; FIND_NME=true;

end else if W[t]<W[NME[i]] then NME[i]:= t;

if NME[j]=0 then begin

NME[j]:= t; FIND_NME=true;

end else if W[t]<W[NME[j]] then NME[j]:= t;

end;

end;

end;

Временная сложность алгоритма Борувки есть O(m×log n).

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

procedure MSP_KRASKAL(var ET; var mt; G; n,m);

begin

Отсортировать массив E по невозрастанию весов его элементов;

Создать коллекцию из n синглетонов множества {1, 2, … , n};

mt:= 0;

for i:= 1 to m do begin

Найти имя a подмножества, содержащего элемент E[i][1];

Найти имя b подмножества, содержащего элемент E[i][2];

if a ≠ b then begin

Объединить подмножества коллекции с именами a и b;

mt:= mt+1; ET[mt]:= E[i];

end;

end;

end;

Временная сложность алгоритма Краскала есть O((m+n)×log n)).

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

В данном алгоритме (см. [2]) используется представление исходного графа G окрестностями его вершин. Для окрестности i–ой вершины графа G = (V, E) мы будем использовать введенное обозначение O_G(i). При этом заметим, что при непосредственном программировании следует использовать структуру ADJ[1..n]. В алгоритме используются также массивы

· a[1..n] (a[x] - вес минимального по весу ребра, соединяющего вершину x с построенным фрагментом минимального остова),

· b[1..n] (b[x] - имя второй вершины этого ребра) и

· VT[1..n] (VT[y]=1, если вершина y входит в построенный фрагмент минимального остова).

Алгоритм начинает свою работу с любой вершины uÎV. Для определенности положим, что u является первой вершиной.

procedure MSP_PRIM(var ET; var mt; G; n,m);

begin

for i:= 1 to n do VT[i]:= 0; mt:= 0; u=1; VT[u]:= 1;

for xÎO_G(u) do begin

a[x]:= W(x,u); b[x]:= u;

end else a[x]:= +¥;

while mt<n-1 do begin

u:= argmin{a[x] : VT[x]:= 0};

if a[u]:= +¥ then begin writeln(‘граф несвязен’); exit; end;

q:= b[u];

VT[u]:= 1; mt:= mt+1;

ET[mt][1]:= u; ET[mt][2]:= q;

for xÎO_G(u) do if VT[x]=0 then if a[x]>W(x,u) then begin

a[x]:= W(x,u); b[x]:= u;

end;

end;

end;

Временная сложность алгоритма Прима есть O(n²).

Примечание.Используемый в псевдокоде знак +¥ обозначает число, которое больше веса любого ребра исходного графа G.

Round Robin алгоритм

procedure MSP_RRA(var ET; var mt; G; n,m);

begin

mt:= 0;

Создать пустую коллекцию K разделенных подмножеств множества V;

Создать пустой двусторонний список Q корневых элементов разделенных множеств из K;

for uÎV do begin Создать(u, K); Добавить u к концу списка Q;

Создать ленивую левостороннюю кучу H(u) из ребер, инцидентных u;

end;

while |Q|>1 do begin

Изъять первый элемент f из списка Q;

Найти элемент edge минимального веса в куче H(f);

a:= edge[1]; b:= edge[2]; Найти(i,a,K); Найти(j,b,K);

if i¹j then begin

mt:= mt+1; ET[mt]:= edge;

Удалить i и j из списка Q;

Объединить(i,j,K);

z:= корневой элемент подмножества, полученного объединением подмножеств с корневыми элементами и

i и j;

H(z):= ленивая левосторонняя куча, полученная слиянием куч H[i] и H[j];

Добавить z к концу списка Q;

end;

end;

end;

Временная сложность Round Robin алгоритма есть O(m×log log n).

Примечание.Элемент (ребро) в ленивой куче H[t] считается пустым, если концы этого ребра принадлежат одному и тому же множеству из коллекции K.

Задания для лабораторной работы № 2

Предлагается попарное сравнение различных алгоритмов нахождения минимального по весу остовного дерева в графе G = (V, E), имеющего n вершин и m ребер.

Варианты выбора пары алгоритмов A и B для сравнения:

Вариант 1

· А - алгоритм Борувки,

· В - алгоритм Краскала;

Вариант 2

· А - алгоритм Борувки,

· В - алгоритм Прима;

Вариант 3

· А - алгоритм Прима,

· В - алгоритм Краскала;

Вариант 4

· А - алгоритм Борувки,

· В - Round Robin алгоритм.

Задание.

1. Написать программу, реализующую алгоритм А и алгоритм В.

2. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:

· число n вершин и число m ребер графа,

· натуральные числа q и r, являющиеся соответственно нижней и верхней границей для весов ребер графа.

Выходом данной программы должно быть время работы Т_А алгоритма А и время работы Т_В алгоритма В в секундах.

3. Провести эксперименты на основе следующих данных:

3.1. n = 1, … ,10⁴+1 с шагом 100, q = 1, r =10⁶, количество ребер: а) m ≈ n²/10, б) m ≈ n² (нарисовать графики функций T_А(n) и Т_В(n) для обоих случаев);

3.2. n = 101, … ,10⁴+1 с шагом 100, q = 1, r = 10⁶, количество ребер: а) m ≈ 100×n, б) m ≈ 1000×n (нарисовать графики функций T_А(n) и Т_В(n) для обоих случаев);

3.3. n = 10⁴+1, m = 0, … ,10⁷ с шагом 10⁵, q = 1, r = 10⁶ (нарисовать графики функций T_А(m) и Т_В(m) );

3.4. n = 10⁴+1, q = 1, r = 1, … ,200 с шагом 1, количество ребер: а) m ≈ n², б) m ≈ 1000×n (нарисовать графики функций T_А(r) и Т_В(r) для обоих случаев).

4. Сформулировать и обосновать вывод о том, в каких случаях целесообразно применять алгоритм А, а в каких - алгоритм В.