Конспект лекции с таймкодами — и карточки к экзамену

Коротко

Лекция о графах: что такое вершины и рёбра, как хранить граф в памяти и как по нему ходить. Для реальных разреженных графов почти всегда подходит список смежности. BFS находит кратчайший путь по числу рёбер, DFS — циклы и компоненты, алгоритм Дейкстры — кратчайший путь во взвешенном графе с неотрицательными весами.

Главное

• 0:11Граф — это вершины и рёбра; рёбра бывают направленными и взвешенными.
• 0:56Матрица смежности проверяет ребро за O(1), но занимает n² памяти.
• 1:28Список смежности занимает O(n + m) — выбор по умолчанию для разреженных графов.
• 2:03BFS обходит граф слоями через очередь и находит кратчайший путь по числу рёбер.
• 2:50DFS идёт вглубь через стек или рекурсию: циклы, компоненты, топологическая сортировка.
• 3:49Отмечайте вершину посещённой при добавлении в очередь, а не при извлечении.
• 4:13Дейкстра берёт ближайшую необработанную вершину из кучи: O((n + m) log n).
• 4:37С отрицательными весами Дейкстра не работает — нужен Беллман — Форд.

Главы

1. 0:00Что такое граф
2. 0:47Как хранить граф
3. 1:52Поиск в ширину
4. 2:50Поиск в глубину
5. 4:01Алгоритм Дейкстры
6. 5:01Итоги и домашнее задание

Термины

Список смежности 1:28

Для каждой вершины хранится список соседей; память O(n + m).

BFS 2:03

Обход слоями с очередью; кратчайший путь в графе без весов.

DFS 2:50

Обход вглубь со стеком или рекурсией.

Алгоритм Дейкстры 4:13

Кратчайшие пути от одной вершины при неотрицательных весах.