Алгоритмы на графах · интерактивный разбор
Поиск в глубину (DFS)
Нажимайте «Следующий шаг» и проследите, как работает рекурсивный код.
Лааксонен · § 7.2.1 · рис. 7.13
Граф из учебника
не посещенапосещенатекущий вызоврёбра обхода
Подготовка
Начнём с вершины 1
Все значения visited равны false. Первый вызов — dfs(1).
0 / 0Скорость
Код из учебника · C++
Подсветка выполняемой строкиВызов dfs(u) есть для каждого соседа, в том числе уже посещённого. Строка if (visited[s]) return; сразу завершает повторный вызов.
Память алгоритма
visited[1…5]
Порядок обработки
—
Стек рекурсивных вызовов · слева направо
Проверьте себя
До запуска предскажите порядок посещения. Затем найдите момент, когда dfs(5) повторно вызывается из вершины 2. Почему вершина 5 не обрабатывается второй раз?
Порядок соседей в этой симуляции: 1: [2, 4]; 2: [1, 3, 5]; 3: [2, 5]; 4: [1]; 5: [2, 3].
Порядок соседей в этой симуляции: 1: [2, 4]; 2: [1, 3, 5]; 3: [2, 5]; 4: [1]; 5: [2, 3].
Для преподавателя. При старте из вершины 1 порядок первой обработки совпадает с рисунком 7.13: 1 → 2 → 3 → 5 → 4. Кнопка «Назад» позволяет отдельно обсудить возврат из рекурсии, проверку visited и переход к следующему соседу. При другом порядке соседей DFS может дать другой порядок обхода.