Графы — поиск в ширину и глубину

  • В этой теме 0 ответов, 1 участник, последнее обновление 3 недели, 6 дней назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #7099
      @admin

      В этой заметке описаны алгоритмы обхода графа в глубину и в ширину, при этом не указывается каким именно образом представлен граф. Тем не менее, способ хранения графа будет влиять на асимптотическую сложность алгоритма, так например — типичной операцией при обходе является проверка наличия дуги из вершины A в вершину B, однако при задании графа в виде матрицы смежности для этого потребуется O(1) операций, а при задании в виде списков смежности — O(n).

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

      Алгоритмы поиска хранят список уже посещенных вершин или помечают посещенные вершины другим образом. Это необходимо чтобы не зацикливаться – иначе можно вечно переходить из вершины A в вершину B и назад.

      Рассматривать алгоритмы будем на таком графе:

      Поиск в глубину

      На каждом шаге поиска в глубину алгоритм выбирает новую вершину, смежную с текущей и продолжает поиск уже из нее. Такое «углубление» продолжается до тех пор, пока не будет найдена вершина, смежная с конечной или алгоритм не зайдет в тупик.

      Пусть надо найти путь из вершины S в вершину F. Поиск в глубину (DFS) работает следующим образом:
      1. Если номера вершин S и F совпали – путь найден (восстановить его можно раскрутив стек);
      2. Если из вершины S есть дуга вершину X и вершина X не была посещена ранее – то найти путь из X в F рекурсивно.
      3. Второй шаг выполняется для всех вершин, в которые можно перейти из S.
      4. Если все дуги из S обработаны и ни по одной из них не был найден путь – значит такого пути нет.

      Алгоритм поиск в глубину находит путь, который не обязательно является кратчайшим. Он очень прост и хорошо подходит если надо проверить наличие пути (найти любой путь). Если же нужен кратчайший путь – применяется поиск в ширину. Так, например, для приведенного выше графа при поиске пути из вершины 5 в вершину 6 алгоритм dfs даст путь «5 -> 1 -> 3 -> 6», хотя есть более короткий «5 -> 6».

      Более формальное описание алгоритма:
      1. начало; функция breadth(G, Start, Finish)
      ; обход графа в ширину
      ; G — граф,
      ; Finish — начальная вершина,
      ; Start — конечная вершина
      2. пометить вершину Start как обработанную;
      3. выбрать дугу (Start, X), такую, что вершина X не обработана, если дуги нет — переход на п.4;
      3.1. если в G есть дуга (Start, Finish) — вернуть (true, (Start, Finish));
      3.2. (Res, Path) := breadth(G, X, Finish);
      3.3. если Res = true — вернуть (true, (Start, X) + Path);
      3.4. вернуть breadth(G, Start, Finish);
      4. конец — вернуть (false, ()).

      В результате рекурсивного вызова (п. 3.2) может быть найден путь, проходящий через одну из смежных со Start дуг. Если путь найден — то его необходимо дополнить соответствующей дугой (п.3.3), в противном случае — перейти к поиску пути, проходящему через другую дугу (п. 3.4).

      Стоит отметить, что на шаге 3 алгоритма листинг 1 выбирается произвольная дуга, однако, выбор дуга влияет на результат, т.к. алгоритм не гарантирует что найденный путь будет кратчайшим. Например, если при поиске пути из вершины P а вершину F, первой будет выбрана дуга (P, D), то будет найден путь (P, D, F), однако, если первой будет взята дуга (P, B), то может быть найден путь (P, B, C, D, F).

      1.2 Обход графа в ширину

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

      Поиск в ширину

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

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×