Обходы графов по ширине и по глубине

Пусть G = (М, R) — связный неориентированный граф, Т — некоторый остов графа G, a — некоторая фиксированная вершина, называемая корнем дерева Т.

Разместим вершины из М по этажам таким образом, чтобы корень а находился в верхнем этаже, смежные с ним вершины занимали этаж на единицу ниже, смежные с отмеченными вершинами — еще на единицу ниже и т. д.

Таким образом, получаем е (а) + 1 этажей, где е (а) — эксцентриситет вершины а.

1) Обход графа по глубине.

После очередной рассмотренной вершины выбирается смежная с ней вершина следующего этажа;

Если следующая вершина висячая и ее достижение не дает желаемого решения задачи, то возвращаемся до ближайшей вершины степени > 3 и просматриваем вершины другого, еще, не пройденного маршрута в таком же порядке и т. д

2) Обход графа по ширине.

Просмотр вершин дерева ведется по этажам, переход к следующему этажу производится только после просмотра всех вершин данного этажа.

Очевидно, что при обходе всех вершин оба подхода: поиск в глубину и поиск по ширине — эквивалентны. Выбор обхода графа в поиске нужной вершины определяется структурой дерева.

Если дерево «широкое» и «короткое» (висячие вершины расположены на сравнительно близких этажах), то используем поиск по глубине.

Для глубоких узких деревьев, когда висячие вершины могут встретиться на различных этажах и их разброс по этажам достаточно велик, используем поиск по ширине.

Пример: граф G на рисунке имеет восемь граней: Г₁,Г₂,...,Г₈. Неограниченная грань Г называется внешней, а остальные грани Г₂,Г₃,...,Г₈ — внутренними.