Правила форума
Лекция №12.3: Алгоритмы на графах и деревьяхСодержание
Прямой обход
Прямой обход произвольного связного графа
Для простоты изложения будем считать, что граф задан матрицей смежности, которая хранится в квадратном массиве sm. Дополнительный линейный массив mark хранит информацию о последовательности посещения вершин:
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
- Начать с корня дерева.
- Совершить обратный обход левого поддерева.
- Совершить обратный обход правого поддерева.
- Пометить текущую вершину.
Замечание: Этот алгоритм также может быть распространён на случай произвольного корневого дерева.
/12%2D3.gif)
Рис. 12.3. Последовательность нумерации вершин при обратном обходе дерева
Реализация
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 — о фактах их посещения:
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
- Начать с корня дерева.
- Совершить прямой обход левого поддерева.
- Пометить текущую вершину.
- Совершить прямой обход правого поддерева.
Замечание: Этот обход специфичен только для бинарных деревьев, поэтому невозможно применить его к произвольному графу, каркасом которого совершенно не обязательно будет именно бинарное дерево.
Реализация
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.
::
::
::
