Geum.ru

Лекция 12: Алгоритмы на графах и деревьях

Вид материалаЛекция

Содержание


Генерация дерева синтаксического анализа
Построение из инфиксной записи
Алгоритм Infix
Построение из префиксной записи
Алгоритм Prefix
Построение из постфиксной записи
Алгоритм Postfix
Обходы деревьев и графов
Прямой обход
Алгоритм PreOrder
Прямой обход произвольного связного графа
Обратный обход
Алгоритм PostOrder
Обратный обход произвольного связного графа
Синтаксический обход
Алгоритм SyntOrder
Подобный материал:

Лекция 12: Алгоритмы на графах и деревьях



Примеры алгоритмов обработки деревьев и графов. Сравнение рекурсивных и итеративных алгоритмов, решающих некоторые классические задачи теории графов.







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

Используемая здесь терминология полностью совпадает с терминологией, введенной в предыдущей лекции.
^

Генерация дерева синтаксического анализа


Одно и то же арифметическое выражение может быть записано тремя способами:
  1. Инфиксный способ записи (знак операции находится между операндами):

((a / (b + c)) + (x * (y - z)))

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

+( /(a, +(b,c)), *(x, -(y,z)))

Из знакомых всем нам функций префиксный способ записи используется, например, для sin(x), tg(x), f(x,y,z) и т.п.
  1. Постфиксный способ записи (знак операции находится после операндов):

((a,(b,c)+ )/ ,(x,(y,z)- )* )+

Этот способ записи менее распространен, однако и с ним многим из нас приходилось сталкиваться уже в школе: примером будет n! (факториал).

Разумеется, вид дерева синтаксического анализа (ДСА)1) арифметического выражения не зависит от способа записи этого выражения (см. рис. 12.1), поскольку определяет его не форма записи, а порядок выполнения операций. Но процесс построения дерева, конечно же, зависит от способа записи выражения. Далее мы разберем все три варианта алгоритма построения ДСА.


Рис. 12.1.  Дерево синтаксического анализа и способ описания его элементов

type ukaz = ^tree;

tree = record

symbol: char;

left: ukaz;

right: ukaz;

end;
^

Построение из инфиксной записи


Для простоты мы будем считать, что правильное арифметическое выражение подается в одной строке, без пробелов, а каждый операнд записан одной буквой. Приоритет операций определяется расставленными скобками: ими должна быть снабжена каждая операция.
^
Алгоритм Infix

Если не достигнут конец строки ввода, прочитать очередной символ.

Если этот символ - открывающая скобка, то:
  1. создать новую вершину дерева;
  2. вызвать алгоритм Infix для ее левого поддерева;
  3. прочитать символ операции и занести его в текущую вершину;
  4. вызвать алгоритм Infix для правого поддерева;
  5. прочитать символ закрывающей скобки (и ничего с ним не делать).

Иначе:
  1. создать новую вершину дерева;
  2. занести в нее этот символ.
Реализация

Мы воспользуемся здесь описанием типа данных ukaz, приведенным на рис. 12.1:

procedure infix(var p: ukaz);

var c: char;

begin

read(c);

if c = '('

then begin

new(p);

infix(p^.left);

read(p^.symbol); {'+', '-', '*', '/'}

infix(p^.right);

read(c); {')'}

end

else begin {'a'..'z','A'..'Z'}

new(p);

p^.symbol:= c;

p^.right:= nil;

p^.left:= nil

end;

end;


begin

...

infix(root);

...

end.
^

Построение из префиксной записи


Для простоты предположим, что правильное арифметическое выражение подается в одной строке, без пробелов, а каждый операнд записан одной буквой. Кроме того, будем считать, что из записи удалены все скобки: это вполне допустимо, так как операция всегда предшествует своим операндам, следовательно, путаница в порядке выполнения невозможна.
^
Алгоритм Prefix
  1. Если не достигнут конец строки ввода, прочитать очередной символ.
  2. Создать новую вершину дерева, записать в нее этот символ.
  3. Если символ - операция, то:
    1. вызвать алгоритм Prefix для левого поддерева;
    2. вызвать алгоритм Prefix для правого поддерева.
Реализация

Вновь воспользуемся описанием типа данных ukaz, приведенным на рис. 12.1:

procedure prefix(var p: ukaz);

begin

new(p);

read(p^.symbol);

if p^.symbol in ['+','-','*','/']

then begin prefix(p^.left);

prefix(p^.right);

end

else begin p^.left:= nil;

p^.right:= nil;

end

end;


begin

...

prefix(root);

...

end.
^

Построение из постфиксной записи


Для простоты предположим, что правильное арифметическое выражение подается в одной строке, без пробелов, а каждый операнд записан одной буквой. Кроме того, снова будем считать, что из записи удалены все скобки.
^
Алгоритм Postfix
  1. Если не достигнут конец строки ввода, прочитать очередной символ,если этот символ - операнд, то занести его в стек1),иначе (символ - операция):
    1. создать новый элемент, записать в него эту операцию;
    2. достать из стека два верхних (последних) элемента, присоединить их в качестве левого и правого операндов в новый элемент;
    3. занести полученный "треугольник" в стек.

По окончании работы этого алгоритма в стеке будет содержаться ровно один элемент - указатель на корень построенного дерева.
Реализация

Для того чтобы упростить работу, добавим в структуру элемента дерева (см. рис. 1.12) дополнительное поле next:ukaz, которое будет служить для связки стека:

stek:= nil;

while not eof(f) do

begin

new(p);

read(f,p^.symbol);

if p^.symbol in ['+','-','*','/']

then begin

p^.right:= stek;

p^.left:= stek^.next;

p^.next:= stek^.next^.next;

stek:= p

end

else begin

p^.left:= nil;

p^.right:= nil;

p^.next:= stek;

stek:= p

end;

end;
^

Обходы деревьев и графов


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

Обход дерева - это некоторая последовательность посещения всех его вершин.

Обход графа - это обход некоторого его каркаса.

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

Напомним, что структуру бинарного дерева мы описываем следующим образом:

type ukazatel = ^tree;

tree = record mark: integer;

left: ukazatel;

right: ukazatel;

end;

Итак, приступим теперь к изучению различных вариантов обхода деревьев и графов.
^

Прямой обход

Другие названия

Префиксный обход: результатом прямого обхода2) дерева синтаксического анализа арифметического выражения будет префиксный вариант записи этого выражения.

Обход в глубину "сверху вниз": название имеет смысл лишь в случае стандартного расположения дерева корнем кверху.
^
Алгоритм PreOrder
  1. Начать с корня дерева.
  2. Пометить3) текущую вершину.
  3. Совершить прямой обход левого поддерева.
  4. Совершить прямой обход правого поддерева.

Замечание: Этот алгоритм может быть естественным образом распространен и на случай произвольного корневого дерева.
Реализация

procedure preorder(p:ukaz; k:integer);

begin p^.mark:= k;

if p^.left<>nil then preorder(p^.left,k+1);

if p^.right<>nil then preorder(p^.right,k+1);

end;


begin

...

preorder(root,1); {Вызов из тела программы}

...

end.


Рис. 12.2.  Последовательность нумерации вершин при прямом обходе дерева
^
Прямой обход произвольного связного графа

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

procedure preorder_graph(v: byte);

var i: byte;

begin

k:= k+1;

mark[v]:= k; {текущей вершине v присвоен порядковый номер}

for i:= 1 to n do

if (mark[i]=0)and(sm[v,i]=1) {есть ребро из текущей вершины v

в еще не помеченную вершину i}

then preorder_graph(i);

end;


begin

...

k:= 0;

preorder_graph(start); {Вызов из тела программы}

...

end.
^

Обратный обход

Другие названия

Постфиксный обход: результатом обратного обхода ДСА арифметического выражения будет постфиксный вариант записи этого выражения.

Обход в глубину "снизу вверх": название имеет смысл лишь в случае стандартного расположения дерева корнем кверху.
^
Алгоритм PostOrder
  1. Начать с корня дерева.
  2. Совершить обратный обход левого поддерева.
  3. Совершить обратный обход правого поддерева.
  4. Пометить текущую вершину.

Замечание: Этот алгоритм также может быть распространен на случай произвольного корневого дерева.


Рис. 12.3.  Последовательность нумерации вершин при обратном обходе дерева
Реализация

procedure postorder(p:ukaz; k:integer);

begin if p^.left<>nil then postorder(p^.left,k+1);

if p^.right<>nil then postorder(p^.right,k+1)

p^.mark:=k;

end;


begin

...

postorder(root,1); {Вызов из тела программы}

...

end.
^
Обратный обход произвольного связного графа

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

procedure postorder_graph(v:byte);

var i: integer;

begin

posesh[v]:=1; {текущая вершина v стала посещенной}

for i:=1 to n do

if (posesh[i]=0)and(sm[v,i]=1) {есть ребро из текущей вершины v

в еще не помеченную вершину i}

then postorder_graph(i);

inc(k);

mark[v]:=k; {текущей вершине v

присвоен порядковый номер}

end;


begin

...

k:=0;

postorder_graph(start); {вызов из тела программы}

...

end.
^

Синтаксический обход

Другие названия

Инфиксный обход: результатом синтаксического обхода ДСА арифметического выражения будет инфиксный вариант записи этого выражения.

Обход "слева направо": название имеет смысл лишь в случае стандартного расположения дерева корнем кверху.
^
Алгоритм SyntOrder
  1. Начать с корня дерева.
  2. Совершить прямой обход левого поддерева.
  3. Пометить текущую вершину.
  4. Совершить прямой обход правого поддерева.

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

procedure syntorder(p:ukaz; k:integer);

begin if p^.left<>nil then syntorder(p^.left,k+1);

p^.mark:=k;

if p^.right<>nil then syntorder(p^.right,k+1);

end;


begin

...

syntorder(root,1); {Вызов из тела программы}

...

end.



Обход в ширину

Последовательность обхода
  1. Пометить вершину 0-го уровня (корень дерева).
  2. Пометить все вершины 1-го уровня.
  3. Пометить все вершины 2-го уровня.
  4. ...


Рис. 12.4.  Последовательность нумерации вершин при синтаксическом обходе дерева

Замечание: Этот алгоритм может быть естественным образом распространен и на случай произвольного корневого дерева.

Алгоритм WideOrder
  1. Занести в очередь1) корень дерева.
  2. Пока очередь не станет пустой, повторять следующие действия:
    1. удалить первый элемент из головы очереди;
    2. добавить в хвост очереди всех потомков удаленной вершины.

Реализация

Для простоты реализации вновь пополним структуру дерева полем next:ukaz, которое будет служить для связки очереди:

head:= root;

tail:= root;

k:= 0;

repeat

tail^.next:= head^.left;

if head^.left<>nil then tail:= tail^.next;

tail^.next:= head^.right;

if head^.right<>nil then tail:= tail^.next;

inc(k);

head^.znachenie:= k; {можно write(head^.znachenie);}

head:= head^.next

until head = nil;


Рис. 12.5.  Последовательность нумерации вершин при обходе дерева в ширину

Древесная сортировка

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

Алгоритм TreeSort
  1. Для сортируемого множества элементов построить дерево двоичного поиска:
    • первый элемент занести в корень дерева;
    • для всех остальных элементов: начать проверку с корня; двигаться влево или вправо (в зависимости от результата сравнения с текущей вершиной дерева) до тех пор, пока не встретится такой же элемент, либо пока не встретится nil. Во втором случае нужно создать новый лист в дереве, куда и будет записано значение нового элемента.
  2. Совершить синтаксический обход построенного дерева, печатая каждую встреченную вершину столько раз, сколько было ее вхождений в сортируемый набор.

Реализация

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

new(root);

read(f,root^.chislo);

root^.kol:= 1;

root^.left:= nil;

root^.right:= nil;

while not eof(f) do

begin

read(f,x);

p:= root;

while true do

begin

if x = p^.chislo

then begin inc(p^.kol);

break

end;


if x > p^.chislo

then if p^.right <> nil

then p:= p^.right

else begin new(p^.right);

p:= p^.right;

p^.chislo:= x;

p^.kol:= 1;

p^.left:= nil;

p^.right:= nil;

break

end


(* x < p^.chislo *)

else if p^.left <> nil

then p:= p^.left

else begin new(p^.left);

p:= p^.left;

p^.chislo:= x;

p^.kol:= 1;

p^.left:= nil;

p^.right:= nil;

break

end

end;

end;



Подсчет количества компонент связности

Задача. Определить количество компонент связности в заданном графе.

Рекурсивный алгоритм

Считаем, что граф задан матрицей смежности sm.

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

Алгоритм КомпСвяз-Рек
  1. Совершить обход в глубину всех компонент связности графа, помечая вершины каждой из них отдельным номером.

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

По окончании работы программы переменная kol будет содержать количество найденных компонент связности.

Реализация

procedure step (v: integer);

var j: integer;

begin

mark[v]:= k;

for j:=1 to N do

if (mark[j]=0)and(sm[v,j]<>0) then step(j);

end;


begin

...

for i:= 1 to N do mark[i]:=0;

k:= 0; {номер текущей компоненты связности}

for i:= 1 to N do

if mark[i]=0 then

begin inc(k);

step(i);

end;

...

end.

Итеративный алгоритм

Для этого алгоритма удобно, чтобы граф был представлен списком ребер.

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

Алгоритм КомпСвяз-Итер

Прочитать начало и конец очередного ребра. Далее возможны 4 различные ситуации:
  1. Оба конца ребра еще не относятся ни к одной из ранее встретившихся компонент связности (mark[u]=0 и mark[v]=0). В этом случае количество компонент связности kol увеличивается на единицу, а новая компонента связности получает очередной номер ks+1.
  2. Один конец ребра уже относится к какой-то компоненте связности, а второй - еще нет (mark[u]=0, а mark[v]<>0). В этом случае общее количество компонент связности kol остается прежним, а непомеченный конец ребра получает ту же пометку, что и второй его конец.
  3. Оба конца нового ребра относятся к одной и той же компоненте связности (mark[u]= mark[v]<>0). В этом случае не нужно производить никаких действий.
  4. Концы нового ребра относятся к разным компонентам связности (0mark[u]mark[v]0). В этом случае нужно объединить две ранее созданные компоненты связности в одну. Общее количество компонент связности kol уменьшается на 1, а все вершины, принадлежавшие к более новой компоненте связности (больший номер), получают новую пометку. Заметим, что переменная ks, обозначающая очередной свободный номер для следующей компоненты связности, в данном случае изменяться не должна, поскольку нет никакой гарантии, что изменен будет номер именно самой последней компоненты связности.

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

Реализация

kol:=0;

ks:=0;

while not eof(f) do

begin

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);

end

end;

for i:=1 to N do

if mark[i]=0 then inc(kol);



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

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

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

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

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

Рекурсивный алгоритм

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

Этот алгоритм базируется на прямом обходе графа, который учитывает два условия: во-первых, чтобы суммарный вес текущего каркаса был меньше текущего минимума и, во-вторых, чтобы в каркасе было ровно N-1 ребро1) (N - количество вершин графа).

Реализация

procedure step(v,k: byte; r: longint);

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.

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

Итеративный алгоритм

Алгоритм Краскала
  1. Упорядочить все ребра графа по возрастанию их весов.
  2. Применить алгоритм КомпСвяз-Итер (см. пункт "Подсчет количества компонент связности").

Замечание: Выполнение алгоритма Краскала можно завершить сразу же, как только в каркас будет добавлено (N-1)-е ребро (поскольку в дереве с N вершинами должно быть ровно N-1 ребро).

Реализация

Реализация основной части алгоритма (шаг 2) совпадает с реализацией алгоритма КомпСвяз-Итер, за исключением того, что в случаях 1, 2 и 4 необходимо ввести подсчет добавленных в каркас ребер, а внешний цикл завершить не в момент достижения конца файла, а в момент, когда счетчик добавленных ребер станет равным N-1.

Нахождение кратчайших путей

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

Рекурсивный алгоритм

Алгоритм Расст-Рек

Совершить обход графа в глубину, при каждом "шаге вперед" прибавляя длину ребра к длине текущего пути, при каждом возврате - отнимая длину этого ребра от длины текущего пути. При движении "вперед" пометки посещенности вершин ставятся, при "откате" - снимаются. По достижении выделенной вершины t производится сравнение длины текущего пути с ранее найденным минимумом.

Реализация

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

procedure rasst(v: byte; r: longint);

var i: byte;

begin

if v = t

then if r< min then min:= r

else

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 итераций.

Алгоритм Дейкстры
  1. Расстояние от s до s, конечно же, равно 0. Кроме того, это расстояние уже никогда не сможет стать меньше - ведь веса всех ребер графа у нас положительны. Таким образом:

dist[s]:= 0; done[s]:= true; last:= s;
  1. Повторить N-1 раз следующие действия:
    1. для всех непомеченных вершин х, связанных ребром с вершиной last, необходимо пересчитать расстояние:

dist[x]:= min(dist[x], dist[last]+ sm[last,x]);
    1. среди всех непомеченных вершин найти минимум в массиве dist: это будет новая вершина last;
    2. пометить эту новую вершину в массиве done.

Реализация

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

dist[s]:= 0;

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. Комментарии, как говорится, излишни.