Методы обхода графа

Решение многих задач на графах основывается на полном обходе графа. Такой обход можно выполнить многими способами, но наибольшее распространение получили две стратегии – поиск в ширину и поиск в глубину. Оба эти метода можно рассматривать как конкретные реализации общего плана обхода, состоящего в следующем.

Обход начинается в заранее выбранной стартовой вершине и состоит в систематическом исследовании ребер и посещении вершин. Какие именно действия выполняются при этом, зависит от конкретной задачи, для решения которой и выполняется обход. Но в любом случае тот факт, что данная вершина посещена, запоминается. Вершину, которая еще не посещена, будем называть новой. В результате посещения вершина становится открытой и остается такой, пока не будут исследованы все инцидентные ей ребра. После этого она превращается в закрытую.

Очередной шаг обхода начинается с выбора какой-либо вершины из множества открытых, она становится активной. Если в окрестности активной вершины есть неисследованные вершины (вершина могла уже быть активной раньше и ее окрестность может быть частично исследована), то выбирается такая вершина . Если новая, то она посещается, ребро при этом классифицируется как прямое. Если же не новая, то ребро считается обратным (ведущим в уже посещенную вершину). Если все вершины из окрестности активной вершины уже исследованы, она становится закрытой. Эти действия повторяются до тех пор, пока множество открытых вершин не станет пустым. Если при этом еще остались новые вершины, то выбирается и посещается одна из таких вершин и процесс повторяется.

По окончании обхода прямые ребра образуют каркас графа. В основе большинства применений поиска в ширину и поиска в глубину лежат свойства этого каркаса.

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