Программирование

• 0) a;
• 1) b, d;
• 2) b, d, c (пути adb, abd, abc);
• 3) c (путь adbc).

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

1. из листьев не выходит ни одна дуга; из других вершин может выходить сколько угодно дуг;
2. в корень не заходит ни одна дуга; во все остальные вершины заходит ровно по одной дуге.

1. существует ровно одна вершина, помеченная любым числом из множества S;
2. все пометки левого поддерева строго меньше, чем пометка текущей вершины;
3. все пометки правого поддерева строго больше, чем пометка текущей вершины.

¹⁾   Ныне - Калининград.
²⁾   Более корректно: Е - это множество двухэлементных подмножеств (неупорядоченных пар) множества V, называемых ребрами. Из такого определения видно, что любые две вершины могут быть соединены не более чем одним ребром.

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

Одно и то же арифметическое выражение может быть записано тремя способами:

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

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

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

2. Префиксный способ записи (знак операции находится перед операндами):

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

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

3. Постфиксный способ записи (знак операции находится после операндов):

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

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

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

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

type ukaz = ^tree;
     tree = record
             symbol: char;
             left: ukaz;
             right: ukaz;
       end;

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

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

Алгоритм Infix

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

Если этот символ - открывающая скобка, то:

Иначе:

Реализация

Мы воспользуемся здесь описанием типа данных 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

Реализация

Вновь воспользуемся описанием типа данных 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.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;

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

Прямой обход

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

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

Обход в глубину "сверху вниз": название имеет смысл лишь в случае стандартного расположения дерева корнем кверху.

Алгоритм PreOrder

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

Реализация

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.

Рис. 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. Пометить текущую вершину.

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

Рис. 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. ...

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

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

Алгоритм WideOrder

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;

Рис. 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 операций. Следовательно, общая сложность алгоритма может быть приблизительно оценена значением N³/8. Возможное количество вершин графа ограничено только максимальным размером линейного массива (32 000).

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

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

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

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

Этот алгоритм базируется на прямом обходе графа, который учитывает два условия: во-первых, чтобы суммарный вес текущего каркаса был меньше текущего минимума и, во-вторых, чтобы в каркасе было ровно N-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.

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

Алгоритм, предложенный Дейкстрой, настолько мощнее рекурсивного алгоритма Расст-Рек, что, при тех же начальных условиях и не прикладывая дополнительных усилий, он может найти расстояние от выделенной вершины s не только до одной вершины t, но и до всех остальных вершин графа.

Итак, пусть граф задан матрицей смежности.

Линейный массив dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt, символизирующими "бесконечность". По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.

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

Переменная last будет хранить номер последней помеченной вершины.

Отметим особо, что на каждом шаге Алгоритм Дейкстры находит длину кратчайшего пути до очередной вершины графа. Именно поэтому достаточно сделать ровно N-1 итераций.

Алгоритм Дейкстры

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

   dist[s]:= 0; done[s]:= true; last:= s;

2. Повторить N-1 раз следующие действия:

   1. для всех непомеченных вершин х, связанных ребром с вершиной last, необходимо пересчитать расстояние:

         dist[x]:= min(dist[x], dist[last]+ sm[last,x]);

   2. среди всех непомеченных вершин найти минимум в массиве dist: это будет новая вершина last;
   3. пометить эту новую вершину в массиве 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!, а алгоритм Дейкстры имеет сложность ~N². Комментарии, как говорится, излишни.