Обход по уровням

Обход в глубину

При обходе в глубину происходит посещение первого узла, а затем передвиже­ние вдоль ребер графа, пока не будет достигнут тупик. Узел неориентированного графа является тупиком, если уже посещены все примыкающие к нему узлы. В ориентированном графе тупиком также оказывается узел, из которого нет вы­ходящих ребер.

После попадания в тупик следует вернуться назад вдоль пройденного пути, пока не будет обнаружена вершина, у которой есть еще не посещенный сосед, а затем двигаться в новом направлении. Процесс оказывается завершенным после того, как произошел возврат в отправную точку, а все примыкающие к ней вершины уже посещены (рис. 14.30).

При реализации алгоритма обхода в глубину используется рекурсивный вызов процедуры.

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

Алгоритм обхода вершин графа по уровням приведен на рис. 14.31. В отличие от обхода в глубину, этот алгоритм реализован с использованием очереди. Очередь — это специальный программный механизм, предназначенный для упорядоченного хранения и извлечения данных. При помощи процедуры Enqueue заданный объект помещается в конец очереди, а процедура Dequeue извлекает из начала очереди размещенный там объект. Таким образом, пока идет обработка данных в узлах те­кущего уровня, узлы следующего уровня, связанные ребрами с текущими узлами, помещаются в очередь.

При анализе графов и применении их для решения различных информационных задач используют стандартные алгоритмы поиска минимального пути, поиска пути с минимальным (. максимальным) весом ребер, анализа компонентов двусвязности.

Дата добавления: 2014-01-03