Обход графа

Обход графа (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.