Где применяется
1. Задача
В прошлом уроке ты научился хранить граф списком смежности: у каждого узла свой список прямых соседей. Теперь граф лежит в памяти, и по нему можно ходить.
Возьмём схему метро. Станции это точки (узлы, nodes), перегоны это линии между ними (рёбра, edges). Ты стоишь на одной станции и хочешь знать: до каких станций можно доехать и сколько остановок до каждой?
Такие же вопросы задают про друзей и друзей друзей, про веб-страницы и ссылки между ними, про комнаты и двери. Когда нужно разойтись от одного узла и дойти до остальных, нужен обход графа.
Обход графа сложнее, чем проход по списку, потому что в графе бывают циклы. К одной станции могут вести два пути. Если идти по связям, ничего не отмечая, будешь ходить по кругу бесконечно.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитbfsDistances({0: [1, 2], 1: [0, 2, 3], 2: [0, 1, 4], 3: [1, 5], 4: [2, 5], 5: [3, 4, 6], 6: [5]}, 0)Ищем минимальное число рёбер от вершины 0 до каждой другой. Вершина 0 получает dist 0 и встаёт в очередь.
Как узнать
Эти слова в условии значат этот паттерн
- кратчайший путь в невзвешенном графе
- минимальное число шагов/рёбер между узлами
- достижим ли узел Y из узла X
- исследовать кольцо за кольцом / слой за слоем
- граф задан списком смежности, возможны циклы
Похоже, но не то
- Обход дерева (Tree traversal)
В дереве в узел нельзя попасть дважды, поэтому множество посещённых не нужно. В графе можно, поэтому нужно всегда.
- Алгоритм Дейкстры (Dijkstra's algorithm)
Веса на рёбрах ломают порядок по уровням. Тогда очередь заменяется кучей.
- Компоненты связности (Connected components)
Та страница считает группы в графе. Здесь описан сам обход, из которого счёт и складывается.
- Бэктрекинг (Backtracking)
Бэктрекинг откатывает состояние на выходе. Обход помечает узел и никогда не снимает пометку.
V вершин и E рёбер дают O(V + E). Память O(V) на множество посещённых и на фронт.
На LeetCode
Задачи на граф о том, что достижимо из старта или за сколько наименьших рёбер туда дойти. Поиск в ширину с очередью и множеством visited идёт кольцами, поэтому до каждого узла он впервые доходит по кратчайшему пути.
Построй список смежности, запусти поиск в ширину из source и проверь, попал ли destination в visited.
Ключи в комнате это её рёбра, так что запусти поиск в ширину из комнаты 0 и проверь, что посещены все комнаты.
Обойди граф в ширину, и пусть словарь visited хранит копию каждого узла, чтобы рёбра могли на неё ссылаться.
Слова это узлы, а замена одной буквы это ребро, поэтому расстояния из урока дают самую короткую лесенку.