Обход графа

Обход графа (Traversal of a graph) - последовательность вершин графа, в которой каждая вершина графа содержится ровно один раз. Обходы обычно рассматриваются в связи с некоторыми специальными видами графов, например деревьями. Примерами обхода деревьев являются следующие: префиксный (preorder traversal), постфиксный (postorder traversal), инфиксный (inorder traversal). При обходе деревьев выражений эти три вида обходов приводят соответственно к префиксной (польской), постфиксной (обратной польской) и инфиксной записи выражений, различающейся местом расположения в них знаков операций (символов функций)): перед операндами, после операндов и между операндами соответственно.

Прямая и обратная польские записи --- это способы бесскобочной записи выражений, названные в честь родины ее автора --- Яна Лукашевича.

См. также Базисная нумерация, Нумерация вершин, K-нумерация, L-нумерация, M-нумерация, T-нумерация, Поиск в глубину, Поиск в ширину, Правильная нумерация, Разумная нумерация, Топологическая сортировка, Укладка уграфа

Литература

[Касьянов-Поттосин],

[Словарь],

[Евстигнеев-Касьянов/94]