Обход графа: различия между версиями
Перейти к навигации
Перейти к поиску
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Обход графа''' (''[[Traversal of a graph]]'') | '''Обход графа''' (''[[Traversal of a graph]]'') — | ||
последовательность [[вершина|вершин]] [[граф|графа]], в которой | последовательность [[вершина|вершин]] [[граф|графа]], в которой | ||
каждая вершина графа содержится ровно один раз. Обходы | каждая вершина графа содержится ровно один раз. Обходы | ||
| Строка 5: | Строка 5: | ||
видами графов, например [[дерево|деревьями]]. Примерами обхода деревьев | видами графов, например [[дерево|деревьями]]. Примерами обхода деревьев | ||
являются следующие: ''префиксный'' (preorder traversal), | являются следующие: ''префиксный'' (preorder traversal), | ||
''постфиксный'' (postorder traversal), ''инфиксный'' | ''постфиксный'' (postorder traversal), ''[[инфиксный порядок обхода дерева|инфиксный]]'' | ||
(inorder traversal). При обходе деревьев | (inorder traversal). При обходе деревьев | ||
выражений эти три вида обходов | выражений эти три вида обходов | ||
| Строка 11: | Строка 11: | ||
постфиксной (обратной польской)'' и ''инфиксной | постфиксной (обратной польской)'' и ''инфиксной | ||
записи'' выражений, различающейся местом расположения в | записи'' выражений, различающейся местом расположения в | ||
них знаков операций (символов функций | них знаков операций (символов функций): перед операндами, | ||
после операндов и между операндами соответственно. | после операндов и между операндами соответственно. | ||
Прямая и обратная польские записи | Прямая и обратная польские записи — это способы | ||
бесскобочной записи выражений, названные в честь родины ее | бесскобочной записи выражений, названные в честь родины ее | ||
автора | автора — Яна Лукашевича. | ||
==См. также== | ==См. также== | ||
''[[Базисная нумерация]], [[Нумерация вершин]], [[K-Нумерация|K-нумерация]], [[L-Нумерация|L-нумерация]], [[M-Нумерация|M-нумерация]], [[T-Нумерация|T-нумерация]], [[Поиск в глубину]], [[Поиск в ширину]], [[Правильная нумерация]], [[Разумная нумерация]], [[Топологическая сортировка]], [[Укладка уграфа]]'' | * ''[[Базисная нумерация]],'' | ||
* ''[[Нумерация вершин]],'' | |||
* ''[[K-Нумерация|<math>\,K</math>-нумерация]],'' | |||
* ''[[L-Нумерация|<math>\,L</math>-нумерация]],'' | |||
* ''[[M-Нумерация|<math>\,M</math>-нумерация]],'' | |||
* ''[[T-Нумерация|<math>\,T</math>-нумерация]],'' | |||
* ''[[Поиск в глубину]],'' | |||
* ''[[Поиск в ширину]],'' | |||
* ''[[Правильная нумерация]],'' | |||
* ''[[Разумная нумерация]],'' | |||
* ''[[Топологическая сортировка]],'' | |||
* ''[[Укладка уграфа]].'' | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991. | |||
Версия от 12:09, 26 мая 2011
Обход графа (Traversal of a graph) — последовательность вершин графа, в которой каждая вершина графа содержится ровно один раз. Обходы обычно рассматриваются в связи с некоторыми специальными видами графов, например деревьями. Примерами обхода деревьев являются следующие: префиксный (preorder traversal), постфиксный (postorder traversal), инфиксный (inorder traversal). При обходе деревьев выражений эти три вида обходов приводят соответственно к префиксной (польской), постфиксной (обратной польской) и инфиксной записи выражений, различающейся местом расположения в них знаков операций (символов функций): перед операндами, после операндов и между операндами соответственно.
Прямая и обратная польские записи — это способы бесскобочной записи выражений, названные в честь родины ее автора — Яна Лукашевича.
См. также
- Базисная нумерация,
- Нумерация вершин,
- [math]\displaystyle{ \,K }[/math]-нумерация,
- [math]\displaystyle{ \,L }[/math]-нумерация,
- [math]\displaystyle{ \,M }[/math]-нумерация,
- [math]\displaystyle{ \,T }[/math]-нумерация,
- Поиск в глубину,
- Поиск в ширину,
- Правильная нумерация,
- Разумная нумерация,
- Топологическая сортировка,
- Укладка уграфа.
Литература
- Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
- Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
- Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.