Посещенные
В стеке
Проверенные ребра

  • Текущая
  • В стеке
  • Обработанные
  • Путь
Щелчок по вершине задает

Подробнее о поиске в глубину

Поиск в глубину (DFS)

Поиск в глубину исследует граф, как человек, который идет по лабиринту, держась одной рукой за стену: он следует по одному пути так далеко, как только можно, и возвращается, лишь когда идти больше некуда. Для этого он использует стек. Щелкните вершину, чтобы начать с нее, при желании выберите цель и пройдите поиск по шагам: смотрите, как стек растет и уменьшается, как каждая вершина получает номер посещения и какие ребра замыкают цикл. Нажмите Пуск, чтобы посмотреть поиск, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. Щелкните вершину, чтобы сделать ее стартом; переключите щелчок на Цель и щелкните другую вершину, чтобы искать путь к ней. Число на каждой вершине — порядковый номер ее посещения, а ряд под графом — это стек, от старта до вершины наверху. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.

Как это работает

  1. Щелкните вершину, чтобы сделать ее стартом. Чтобы искать путь, переключите щелчок на Цель и щелкните другую вершину.
  2. Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место поиска.
  3. Следите за стеком под графом и номером посещения на каждой вершине. Кнопка Новый граф создает другой граф для пробы.

Как работает поиск в глубину

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

Что говорит стек

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

Часто задаваемые вопросы

Что такое поиск в глубину?

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

Находит ли поиск в глубину кратчайший путь?

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

Чем DFS отличается от BFS?

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

Как DFS находит цикл?

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

Отправляется ли мой граф куда-нибудь?

Нет. Граф создается и обходится в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор