WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте
Порядок обхода дерева в глубину

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин[1].

Алгоритм поиска в глубину

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

  1. Пройдём по всем вершинам .
    • Если вершина белая, выполним для неё DFS(v).

Процедура DFS (параметр — вершина )

  1. Перекрашиваем вершину в серый цвет.
  2. Для всякой вершины , смежной с вершиной и окрашенной в белый цвет, рекурсивно выполняем процедуру DFS(w)[2].
  3. Перекрашиваем вершину в чёрный цвет.

Часто используют двухцветные метки — без серого, на 1-м шаге красят сразу в чёрный цвет.

Нерекурсивные варианты

На больших графах поиск в глубину серьёзно нагружает стек вызовов. Если есть риск переполнения стека, используют нерекурсивные варианты поиска.

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

Процедура DFS (параметр — вершина )

  1. Кладём на стек пару . Перекрашиваем вершину в серый цвет.
  2. Пока стек не пуст…
    1. Берём верхнюю пару , не извлекая её из стека.
    2. Находим вершину , смежную с и следующую за .
      1. Если таковой нет, извлекаем из стека, перекрашиваем вершину в чёрный цвет.
      2. В противном случае присваиваем , прямо в стеке.
        • Если к тому же вершина белая, кладём на стек пару , перекрашиваем в серый цвет.

Второй вариант: можно в каждой из «серых» вершин держать текущее и указатель на предыдущую (ту, из которой пришли).

Третий вариант работает, если хватает двухцветных меток.

Процедура DFS (параметр — вершина )

  1. Кладём на стек вершину .
  2. Пока стек не пуст…
    1. Берём верхнюю вершину .
    2. Если она белая…
      1. Перекрашиваем её в чёрный цвет.
      2. Кладём в стек все смежные с белые вершины.

Поиск в глубину с метками времени. Классификация рёбер

Поиск в глубину с метками времени. Порядок выбора рёбер — слева направо.

Для каждой из вершин установим два числа — «время» входа и «время» выхода .

Модифицируем процедуру DFS так.

  1. Увеличиваем «текущее время» на 1. .
  2. Перекрашиваем вершину в серый цвет.
  3. Для всякой вершины , смежной с вершиной и окрашенной в белый цвет, выполняем процедуру DFS(v).
  4. Перекрашиваем вершину в чёрный цвет.
  5. Увеличиваем «текущее время» на 1. .

Считаем, что граф ориентированный. Очевидно, для любой вершины, из которой мы не вышли в момент t, . Также невозможно скрёстное неравенство: . Просматриваемые на шаге 3 дуги uv могут быть:

  • . В момент выполнения шага 3 (обозначенный как t) вершина v белая. В таком случае мы для вершины v исполняем DFS, а дуга называется дугой дерева поиска.
  • . В момент t вершина v чёрная, сравнение entry говорит, что в v попали из u. Такая дуга называется прямой.
  • . В момент t вершина v также чёрная, но сравнение entry говорит, что в v попали в обход u. Такая дуга называется перекрёстной.
  • . В момент t вершина v серая, то есть в u попали из v. Имеем дело с обратной дугой.

Рёбра неориентированного графа могут быть рёбрами дерева и обратными, но не прямыми и перекрёстными.[3] Чтобы различать рёбра неориентированного графа, достаточно указанных выше трёх- или двухцветных отметок. Ребро, идущее в белую вершину,— ребро дерева. В серую (чёрную в двухцветном варианте) — обратное. В чёрную — такого не бывает.[4]

Алгоритм Косарайю требует сортировки вершин в обратном порядке по времени выхода. Метка входа и типы рёбер нужны в алгоритмах поиска точек сочленения и мостов.

Применение

Поиск в глубину ограниченно применяется как собственно поиск, чаще всего на древовидных структурах: когда расстояние между точками малó, поиск в глубину может «плутать» где-то далеко.

Зато поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например:

Поиск в глубину — естественный выбор, когда агент (человек или робот) лично ходит по лабиринту и видит то, что непосредственно рядом с ним. «Правило левой руки» (идти, ведя левой рукой по стенке) будет поиском в глубину, если лабиринт древовидный (нет кружных путей).

См. также

Примечания

  1. Cormen, 2005, p. 622.
  2. Обход в глубину, цвета вершин — Викиконспекты
  3. Если в сторону u→v оно прямое, то ранее его прошли в сторону v→u как обратное. Если в сторону u→v оно перекрёстное, его должны были пройти v→u как ребро дерева.
  4. Cormen, 2005, с. 628—629.

Литература

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии