Обход графа: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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.


[Евстигнеев-Касьянов/94]
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.

Навигация