Обход графа: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KVN (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 8: | Строка 8: | ||
(inorder traversal). При обходе деревьев | (inorder traversal). При обходе деревьев | ||
выражений эти три вида обходов | выражений эти три вида обходов | ||
приводят соответственно к ''префиксной (польской), | приводят соответственно к ''префиксной ([[Польская запись|польской]]),'' | ||
постфиксной (обратной польской | ''постфиксной'' ([[Обратная польская запись|''обратной польской'']])и'' инфиксной'' | ||
записи | записи выражений, различающейся местом расположения в | ||
них знаков операций (символов функций): перед операндами, | них знаков операций (символов функций): перед операндами, | ||
после операндов и между операндами соответственно. | после операндов и между операндами соответственно. | ||
| Строка 33: | Строка 33: | ||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | * Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | ||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | * Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | ||
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991. | |||
[[Категория:Деревья]] | |||
[[Категория:Кодогенерация]] | |||
[[Категория:Коды деревьев]] | |||
[[Категория:Неориентированные графы]] | |||
[[Категория:Обыкновенные графы]] | |||
[[Категория:Ориентированные графы]] | |||
[[Категория:Основные термины]] | |||
[[Категория:Потоковый анализ программ]] | |||
[[Категория:Преобразование программ]] | |||
Текущая версия от 10:17, 27 ноября 2024
Обход графа (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.