Главная » Деревья

Чем отличается алгоритм обхода графа от алгоритма обхода вершин дерева

Содержание
  1. Чем отличается алгоритм обхода графа от алгоритма обхода вершин дерева
  2. Прямой обход
  3. Обратный обход
  4. Синтаксический обход
  5. Обход в ширину
  6. Чем отличается алгоритм обхода графа от алгоритма обхода вершин дерева
  7. Алгоритм — тест с ответами

Чем отличается алгоритм обхода графа от алгоритма обхода вершин дерева

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

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

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

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

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

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; for i:= 1 to n do 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. Пометить текущую вершину.

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

Реализация
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; for i:=1 to n do if (posesh[i]=0)and(sm[v,i]=1) then postorder_graph(i); inc(k); mark[v]:=k; 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. 
  
  2. Пометить все вершины 1-го уровня.
    3. 
  
  3. Пометить все вершины 2-го уровня.
    4. 
  
  4. .
    5. 



 

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

    

    3. 



Реализация
Для простоты реализации вновь пополним структуру дерева полем 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; head:= head^.next until head = nil;
 
Источник
 
Чем отличается алгоритм обхода графа от алгоритма обхода вершин дерева
 
Для начала пусть дерево G задано множеством вершин V ( корневая вершина v0 ), дуг - E и Г(v,-) - перечнем потомков вершины v из V.
 
 Обход (пока)дерева вширь (сначала уровень 0, затем 1, и т.д.)
 
будет идти так 0 - 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8, если дерево - такое, как на рис.1
 
уровень: 0 | 0=v0 | /|\ | / | \ | / | \ 1 | 1 2 3 | /| |\ | / | | \ 2 |4 5 6 7 | \ | \ 3 | 8 рис.1.
 
Он потребует использования очереди QUEUE
 
---------- --------------------------- --->|v=>QUEUE|--->|WHILE QUEUE # ПУСТО DO |--------> ---------- ----------+---------------- ---------v--------- ^ | w--+ | Г(w,-) => QUEUE | ------------------- Г(w,-) => QUEUE - запись в очередь всего содержимого Г(w,-)
 
Обход вершин произвольного графа G = < V, E >отличается от обхода дерева лишь тем, что необходимо устранить дублирующее попадание в пройденную вершину. Для этого вводится пометка вершин NEW[V]= 1*TRUE, в стек или очередь заносятся только вершины, помеченные TRUE, при этом их пометка заменяется на FALSE. Следует помнить, что граф может оказаться не связным или некоторые вершины могут быть недостижимы из исходной v0.
 
Чтобы преодолеть эти проблемы, достаточно организовать просмотр начиная с любой ранее не пройденной вершины.
 
Алгоритм поиска вглубь на произвольном графе имеет вид:
 
-------------------- -------------------- ---->| FOR v из V DO |---------->| FOR v из V DO |----> -------------------- -------------------- | ^ | ^ ------v------- | -----v-------- | |NEW[V]:=TRUE|--+ | WALK(v) |--+ -------------- --------------
 
---------------- ----------------------- ----->¦ USE(v) |---->|FOR w из Г(v,-) DO |-----> ¦NEW[V]:=FALSE | ----------------------- ---------------- | ^ -----v----нет | | NEW[w] |----+ ---------- | | да | -----v----- | | WALK(w) |---+ -----------
 
1. Каждая дуга графа анализируется только один раз. 
2. Алгоритм решения задачи легко погружается в этот метод.
 
- определение компонент связности графа за О(m+n) операций 
- при противоположной пометке вершин алгоритм позволяет определять наличие контура в графе.
 
Алгоритм поиска вширь из вершины v0 на произвольном графе имеет вид /первоначально NEW[V] = 1*TRUE/:
 
------------ --------------------------- --->| v0=>QUEUE| ------>| WHILE QUEUE # ПУСТО DO |--------> |NEW[v0]= | -----------+--------------- | FALSE | ------------v----------- ^ ------------ | v = < QUEUE; USE(v) | | | FOR w из Г(v,-) DO |--+ -------+---------------- | ^ ------v---- нет | | NEW[w] |---------+ ------+---- | | да | ------v---------- | | NEW[w]=FALSE | | | w =>STACK |---+ -----------------
 
Пример использования стратегии "разделяй и властвуй" MINMAX(S) - одновременный поиск наибольшего и наименьшего значений на множестве S. Вспомогательные процедуры:
 
MIN_MAX(min,max,s1,s2) - используя одно сравнение находит наименьшее min и наибольшее - max значение среди S= - одного или двух элементов линейно упорядоченного множества (например, чисел) s1 и s2.
 
FMAX(max,s1,s2) - находит наибольшее max, FMIN(min,s1,s2) - наименьшее min среди s1,s2.
 
S -> S1 + S2 - эффективная процедура деления множества S на два примерно равных S1, S2.
 
Исходные данные - множество S исходных значений (к примеру вектор S[1:n]) MINMAX(S,min,max)
 
-----------------да | || S || S1 + S2 | |MIN_MAX(min,max,s1,s2)| | MINMAX(S1,min1,max1)| ----+------------------- | MINMAX(S2,min2,max2)| | | FMIN(min,min1,min2) | | | FMAX(max,max1,max2) | | -------------+--------- | | -----v--- ------------>| RETURN|--> ---------
 
Расчет трудоемкости алгоритма. Пусть T(n) - требуемое коли- чество сравнений для поиска наибольшего и наименьшего значений среди n чисел. Тогда Т(n) определяется следующим соотношением:
 
Решение соотношения: T(n) = 3/2*n - 2 - трудоемкость алгоритма.
 
В случае рекуррентного соотношения
 
его решение имеет следующую асимптотику:
 
Источник
 
Алгоритм — тест с ответами
 
Информатика в настоящее время является стремительно развивающийся наукой. Многие студенты постают в технические университеты, чтобы в будущем связать свою деятельность с IT или приближенными областями. Для проверки знаний по теме Алгоритм предлагаем пройти тестирование на этой странице. Обращаем ваше внимание, что в тесте правильные ответы выделены символом [+].
 
Что называется алгоритмом:
 
[-] а) протокол вычислительной сети
 
[+] б) описание последовательности действий, строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов
 
[-] в) правила выполнения определенных действий
 
Линейным называется алгоритм, если:
 
[+] а) его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий
 
[-] б) он включает в себя вспомогательный алгоритм
 
[-] в) он представим в табличной форме
 
Цикличным называется алгоритм, если:
 
[-] а) он представим в табличной форме
 
[-] б) ход его выполнения зависит от истинности тех или иных условий
 
[+] в) он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий
 
Алгоритм включает в себя ветвление, если:
 
[+] а) ход его выполнения зависит от истинности тех или иных условий
 
[-] б) он включает в себя вспомогательный алгоритм
 
[-] в) он представим в табличной форме
 
Что является свойством алгоритма:
 
[-] б) простота записи на языках программирования
 
Как называется свойство алгоритма, заключающееся в том, что каждое действие и алгоритм в целом должны иметь возможность завершения:
 
Как называется свойство алгоритма, заключающееся в том, что алгоритм должен состоять из конкретных действий, следующих в определенном порядке:
 
Как называется свойство алгоритма, заключающееся в отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях:
 
Как называется свойство алгоритма, заключающееся в том, что один и тот же алгоритм можно использовать с разными исходными данными:
 
Как называется свойство алгоритма, заключающееся в том, что любое действие должно быть строго и недвусмысленно определено в каждом случае:
 
Как называется алгоритм, записанный на “понятном” компьютеру языке программирования:
 
Для того, чтобы алгоритм бинарного поиска работал правильно нужно, чтобы список был:
 
Необходимо определить максимальное количество узлов в двоичном дереве с высотой k, где корень — нулевая высота:
 
Укажите обозначение следующей фразы: “алгоритм X асимптотически более эффективен, чем Y”:
 
[-] а) X будет лучшим выбором для всех входов
 
[-] б) X будет лучшим выбором для всех входов, кроме больших входов
 
[+] в) X будет лучшим выбором для всех входов, за исключением, возможно, небольших входов
 
Чем отличается алгоритм обхода графа от алгоритма обхода вершин дерева:
 
[+] а) графы могут иметь циклы
 
Какой из алгоритмов, перечисленных ниже, будет самым производительным, если дан уже отсортированный массив:
 
[-] б) пирамидальная сортировка
 
На чём основан алгоритм Дейкстры:
 
[-] б) на динамическом программировании
 
Алгоритм, который не основан на жадном подходе:
 
[+] б) алгоритм нахождения кратчайшего пути Беллмана-Форда
 
Источник
 



Читайте также:  Полы дизайнерские из дерева
Оцените статью
© 2024 Деревья и растения