Граф: 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 перетворить їх на картки, тести й подкасти.