Что важно знать
- Большинство реальных графов разреженные — список смежности.
- BFS находит кратчайший путь только без весов.
- Дейкстра не работает с отрицательными весами.
Этап 1 из 15 · ≈ 8 ч
Графы и кратчайшие пути
Основа с Junior
Как представить граф в программе, обходы в ширину и глубину, алгоритм Дейкстры и A*.
Критерии освоения
Junior ≈ 8 ч
- Выбирает между списком смежности и матрицей по размеру и плотности графа
- Решает задачи обхода графа в ширину и в глубину
Практика. Решить пять задач на обход графа — связность, поиск пути, острова на сетке.
Middle ≈ 8 ч
- Находит кратчайший путь алгоритмом Дейкстры и объясняет, когда A* быстрее и почему эвристика должна не переоценивать расстояние
Практика. Реализовать Дейкстру на куче и A* на сетке и сравнить число просмотренных вершин.
Проверка знаний
Войдите, чтобы пройти тест: сданный тест отмечает тему пройденной на карте и в ИПР.
Вопросы с собеседований
Смотреть всеКак представить граф в программе?Junior
Два основных способа: матрица смежности (таблица V×V) и список смежности (для каждой вершины — список соседей).
Полный разборЧем обход в ширину (BFS) отличается от обхода в глубину (DFS)?Junior
BFS идёт по уровням через очередь и находит кратчайший путь по числу рёбер; DFS идёт вглубь до упора через стек или рекурсию.
Полный разборКак работает алгоритм Дейкстры?Middle
Дейкстра находит кратчайшие пути от одной вершины во взвешенном графе с неотрицательными весами: каждый раз берёт ближайшую ещё не обработанную вершину и ослабляет рёбра из неё.
Полный разборЧто такое алгоритм A* и чем он лучше Дейкстры?Middle
A — Дейкстра с подсказкой направления: вершины выбираются по f = g + h, где g — пройденное расстояние, h — оценка остатка до цели.
Полный разбор
Партнёр платформы
Разбор собеседования
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.