Правила форума
Лекция №12.6: Алгоритмы на графах и деревьяхСодержание
Итеративный алгоритм
Сравнение алгоритмов КомпСвяз-Рек и КомпСвяз-Итер
В худшем случае (при полном графе) рекурсивный алгоритм, перебирая все возможные ребра, будет вынужден вызвать основную процедуру (N - 1)! раз. Велика вероятность, что при достаточно большом N произойдёт переполнение оперативной памяти, которое вызовет аварийную остановку программы. Кроме того, размеры квадратной матрицы смежности дают сильное ограничение на возможное количество вершин графа: не более 250 (см. лекцию 3).
Итеративный же алгоритм переберёт все рёбра графа, которых может быть не более, чем N*(N+1)/2. В половине этих случаев возможна ситуация объединения двух компонент связности в одну, для чего потребуется ещё N операций. Следовательно, общая сложность алгоритма может быть приблизительно оценена значением N3/8. Возможное количество вершин графа ограничено только максимальным размером линейного массива (32 000).
Нахождение минимального каркаса
Задача. В заданном взвешенном связном графе определить множество рёбер, составляющих некоторый его оптимальный каркас (например, минимальный по сумме весов входящих в него рёбер).
Рекурсивный алгоритм
Алгоритм Каркас–Рек
Этот алгоритм базируется на прямом обходе графа, который учитывает два условия: во–первых, чтобы суммарный вес текущего каркаса был меньше текущего минимума и, во–вторых, чтобы в каркасе было ровно N-1 ребро1 (N — количество вершин графа).
Реализация
var j : Byte;
begin
if r < min then
if k = N - 1 then
min := r
else
for j := 1 to N do
if (sm[v, j] <> 0) and (mark[j] = 0) then
begin
mark[j] := 1;
step(j, k + 1, r + sm[v, j]);
mark[j] := 0
end;
end;
begin
{...}
for i := 1 to N do
mark[i] := 0;
min := MaxLongInt;
for i := 1 to N do
begin
mark[i] := 1;
step(i, 1, 0);
mark[i] := 0;
end;
WriteLn(min);
{...}
end.
Для того, чтобы помимо суммарного веса каркаса алгоритм также запоминал включённые в каркас рёбра, необходимо добавить дополнительный квадратный массив, в котором будут храниться пометки включения рёбер в каркас.
Итеративный алгоритм
Алгоритм Краскала
- Упорядочить все рёбра графа по возрастанию их весов.
- Применить алгоритм КомпСвяз–Итер (см. пункт «Подсчёт количества компонент связности»).
Замечание: Выполнение алгоритма Краскала можно завершить сразу же, как только в каркас будет добавлено (N-1)–е ребро (поскольку в дереве с N вершинами должно быть ровно N-1 ребро).
Реализация
Реализация основной части алгоритма (шаг 2) совпадает с реализацией алгоритма КомпСвяз–Итер, за исключением того, что в случаях 1, 2 и 4 необходимо ввести подсчёт добавленных в каркас рёбер, а внешний цикл завершить не в момент достижения конца файла, а в момент, когда счётчик добавленных рёбер станет равным N-1.
Нахождение кратчайших путей
Задача. В заданном взвешенном связном графе найти расстояние (длину кратчайшего пути) от выделенной вершины s до вершины t. Веса всех рёбер строго положительны.
Рекурсивный алгоритм
Алгоритм Расст–Рек
Совершить обход графа в глубину, при каждом «шаге вперёд» прибавляя длину ребра к длине текущего пути, при каждом возврате — отнимая длину этого ребра от длины текущего пути. При движении «вперёд» пометки посещённости вершин ставятся, при «откате» — снимаются. По достижении выделенной вершины t производится сравнение длины текущего пути с ранее найденным минимумом.
Реализация
Пусть граф задан матрицей смежности sm, а массив mark хранит информацию о посещениях вершин. Напомним, что уменьшение длины пути «на возврате» совершается рекурсией автоматически, поскольку в её заголовке использован параметр–значение, а вот аналогичное обнуление соответствующих позиций массива mark приходится делать вручную, поскольку задавать массив параметром–значением чересчур накладно:
var i : Byte;
begin
if v = t then
begin
if r < min then
min := r
end
else
for i := 1 to N do
if (mark[i] = 0) and (sm[v, i] <> 0) then
begin
mark[i] := 1;
rasst(i, r + sm[v, i]);
mark[i] := 0
end
end;
begin
{...}
for i := 1 to N do
mark[i] := 0;
min := MaxLongInt;
mark[s] := 1;
rasst(s, 0);
mark[s] := 0;
{...}
end.
Итеративный алгоритм
Алгоритм, предложенный Дейкстрой2, настолько мощнее рекурсивного алгоритма Расст–Рек, что, при тех же начальных условиях и не прикладывая дополнительных усилий, он может найти расстояние от выделенной вершины s не только до одной вершины t, но и до всех остальных вершин графа.
Итак, пусть граф задан матрицей смежности.
Линейный массив dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt, символизирующими «бесконечность». По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.
Ещё один линейный массив done потребуется нам для того, чтобы хранить информацию о том, найден ли уже минимальный путь (он же расстояние) до соответствующей вершины и можно ли исключить эту вершину из дальнейшего рассмотрения.
Переменная last будет хранить номер последней помеченной вершины.
Отметим особо, что на каждом шаге Алгоритм Дейкстры находит длину кратчайшего пути до очередной вершины графа. Именно поэтому достаточно сделать ровно N-1 итераций.
Алгоритм Дейкстры
Расстояние от s до s, конечно же, равно 0. Кроме того, это расстояние уже никогда не сможет стать меньше — ведь веса всех рёбер графа у нас положительны. Таким образом:
dist[s] := 0; done[s] := True; last := s;Повторить N-1 раз следующие действия:
для всех непомеченных вершин х, связанных ребром с вершиной last, необходимо пересчитать расстояние:
dist[x] := min(dist[x], dist[last] + sm[last, x]);- среди всех непомеченных вершин найти минимум в массиве dist: это будет новая вершина last;
- пометить эту новую вершину в массиве done.
Реализация
Мы надеемся, что функцию поиска меньшего из двух целых чисел min, использованную в тексте программы, читатели смогут написать самостоятельно.
done[s] := True;
last := s;
for i := 1 to N - 1 do
begin
for x := 1 to N do
if (sm[last, x] <> 0) and (not done[x]) then
dist[x] := min(dist[x], dist[last] + sm[last, x]);
min_dist := MaxLongInt;
for x := 1 to N do
if (not done[x]) and (min_dist > dist[x]) then
begin
min_dist := dist[x];
last := x;
end;
done[last] := True;
end.
Сравнение алгоритмов Расст–Рек и Дейкстры
Сложность рекурсивного алгоритма пропорциональна N!, а алгоритм Дейкстры имеет сложность ~N2. Комментарии, как говорится, излишни.
Примечания
- ^ См. предыдущую лекцию.
- ^ Dijkstra E.W. A Note on Two Problems in Connection with Graphs, 1959.
::
::
::
