Граф: BFS и DFS
Граф: BFS и DFS — интерактивный эксперимент из приложения «Структуры данных», бесплатной симуляции StudyFi Lab, которая работает прямо в браузере.
Поиск в ширину (BFS) берёт вершины из очереди: сначала все соседи старта, потом их соседи — слой за слоем, поэтому он находит кратчайший путь по числу рёбер. Поиск в глубину (DFS) берёт вершины из стека и уходит как можно дальше, прежде чем вернуться. Оба посещают каждую вершину и ребро один раз: O(V + E). BFS используют навигаторы и «друзья друзей» в соцсетях, DFS — лабиринты и поиск циклов.
Попробуй: Пройди по шагам от вершины 0 и сравни очередь со стеком. Затем выбери стартом вершину 7 — порядок обхода полностью изменится.
Частые вопросы
Что показывает эксперимент «Граф: BFS и DFS»?
Поиск в ширину (BFS) берёт вершины из очереди: сначала все соседи старта, потом их соседи — слой за слоем, поэтому он находит кратчайший путь по числу рёбер. Поиск в глубину (DFS) берёт вершины из стека и уходит как можно дальше, прежде чем вернуться. Оба посещают каждую вершину и ребро один раз: O(V + E). BFS используют навигаторы и «друзья друзей» в соцсетях, DFS — лабиринты и поиск циклов.
Как попробовать «Граф: BFS и DFS»?
Пройди по шагам от вершины 0 и сравни очередь со стеком. Затем выбери стартом вершину 7 — порядок обхода полностью изменится.
Готовишься к контрольной?
Загрузи свои конспекты, и StudyFi превратит их в карточки, тесты и подкасты.