Обход графа: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Обход графа''' (''Traversal of a graph'') - последовательность вершин графа, в которой ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Обход графа''' (''Traversal of a graph'') - | '''Обход графа''' (''[[Traversal of a graph]]'') - | ||
последовательность вершин графа, в которой | последовательность [[вершина|вершин]] [[граф|графа]], в которой | ||
каждая вершина графа содержится ровно один раз. Обходы | каждая вершина графа содержится ровно один раз. Обходы | ||
обычно рассматриваются в связи с некоторыми специальными | обычно рассматриваются в связи с некоторыми специальными | ||
видами графов, например деревьями. Примерами обхода деревьев | видами графов, например [[дерево|деревьями]]. Примерами обхода деревьев | ||
являются следующие: ''префиксный'' (preorder traversal), | являются следующие: ''префиксный'' (preorder traversal), | ||
''постфиксный'' (postorder traversal), ''инфиксный'' | ''постфиксный'' (postorder traversal), ''инфиксный'' | ||
| Строка 18: | Строка 18: | ||
автора --- Яна Лукашевича. | автора --- Яна Лукашевича. | ||
См. также ''Базисная нумерация, Нумерация вершин, K-нумерация, L-нумерация, M-нумерация, T-нумерация, Поиск в глубину, Поиск в ширину, Правильная нумерация, Разумная нумерация, Топологическая сортировка, Укладка уграфа'' | ==См. также== | ||
''[[Базисная нумерация]], [[Нумерация вершин]], [[K-Нумерация|K-нумерация]], [[L-Нумерация|L-нумерация]], [[M-Нумерация|M-нумерация]], [[T-Нумерация|T-нумерация]], [[Поиск в глубину]], [[Поиск в ширину]], [[Правильная нумерация]], [[Разумная нумерация]], [[Топологическая сортировка]], [[Укладка уграфа]]'' | |||
==Литература== | ==Литература== | ||
[Касьянов-Поттосин], | [Касьянов-Поттосин], | ||
Версия от 13:03, 27 ноября 2009
Обход графа (Traversal of a graph) - последовательность вершин графа, в которой каждая вершина графа содержится ровно один раз. Обходы обычно рассматриваются в связи с некоторыми специальными видами графов, например деревьями. Примерами обхода деревьев являются следующие: префиксный (preorder traversal), постфиксный (postorder traversal), инфиксный (inorder traversal). При обходе деревьев выражений эти три вида обходов приводят соответственно к префиксной (польской), постфиксной (обратной польской) и инфиксной записи выражений, различающейся местом расположения в них знаков операций (символов функций)): перед операндами, после операндов и между операндами соответственно.
Прямая и обратная польские записи --- это способы бесскобочной записи выражений, названные в честь родины ее автора --- Яна Лукашевича.
См. также
Базисная нумерация, Нумерация вершин, K-нумерация, L-нумерация, M-нумерация, T-нумерация, Поиск в глубину, Поиск в ширину, Правильная нумерация, Разумная нумерация, Топологическая сортировка, Укладка уграфа
Литература
[Касьянов-Поттосин],
[Словарь],
[Евстигнеев-Касьянов/94]