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

Сравнение алгоритмов КомпСвяз-Рек и КомпСвяз-Итер

Реализация

kol:=0;ks:=0;while not eof(f) dobegin readln(f,u,v); if mark[u]=0 then if mark[v]=0 then begin {случай 1} inc(kol); inc(ks); mark[u]:= ks; mark[v]:= ks; end else mark[u]:= mark[v] {случай 2} else if mark[v]=0 then mark[v]:= mark[u] {случай 2 - симметричный} else if mark[u]<>mark[v] {случай 4} then begin max:= v; min:= u; if u>v then begin max:= u; min:= v end; for i:= 1 to n do if mark[i]= max then mark[i]:= min; dec(kol); endend;for i:=1 to N do if mark[i]=0 then inc(kol);

В худшем случае (при полном графе) рекурсивный алгоритм, перебирая все возможные ребра, будет вынужден вызвать основную процедуру (N-1)! раз. Велика вероятность, что при достаточно большом N произойдет переполнение оперативной памяти, которое вызовет аварийную остановку программы. Кроме того, размеры квадратной матрицы смежности дают сильное ограничение на возможное количество вершин графа: не более 250 (см. лекцию 3).

Итеративный же алгоритм переберет все ребра графа, которых может быть не более чем N*(N+1)/2. В половине этих случаев возможна ситуация объединения двух компонент связности в одну, для чего потребуется еще N операций. Следовательно, общая сложность алгоритма может быть приблизительно оценена значением N³/8. Возможное количество вершин графа ограничено только максимальным размером линейного массива (32 000).

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

Дата добавления: 2014-01-03