IPB

> Лекция №12.3: Алгоритмы на графах и деревьях
Чат
Форум
Загрузка...
 

страницы: 1 2 3 4 5 6

Содержание

Прямой обход

Прямой обход произвольного связного графа

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

procedure preorder_graph(v : Byte);
var i : Byte;
begin
  k := k + 1;
  mark[v] := k;    {текущей вершине v присвоен порядковый номер}
 for i := 1 to n do
   {есть ребро из текущей вершины v в ещё не помеченную вершину i}
   if (mark[i] = 0) and (sm[v, i] = 1) 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
   {есть ребро из текущей вершины v в ещё не помеченную вершину i}
   if (posesh[i] = 0) and (sm[v, i] = 1) 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 2 3 4 5 6

Примечания

 
 К началу страницы 
 

Код для вставки: :: :: :: ГОСТ ::
Поделиться: //
 



-
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"