Графы за 40 минут | самое душное видео для лютых программистов

Полный гайд по алгоритмам поиска на графах для подготовки к собеседованиям! Разбираем DFS (поиск в глубину) и BFS (поиск в ширину) с примерами кода на Python, Java, JavaScript, C++ и Go. Упор делаем на клетчатое 2D поле, которое встречается чаще всего на собеседованиях. 🎯 ЧТО УЗНАЕШЬ: Когда использовать DFS, а когда BFS Как искать путь между точками Поиск кратчайшего маршрута Подсчет компонент связности Проблемы переполнения стека и их решение Оценка сложности в Big O Как рассказывать решение на собеседовании 💻 КОД НА 5 ЯЗЫКАХ: Python Java JavaScript C++ Go ⏱️ ТАЙМКОДЫ: 00:00 - Хай 00:21 - Зачем нужны алгоритмы на графах 00:38 - Про карты 00:46 - Что учитывают карты при построении маршрута 00:56 - Проверка пути на поле из клеток 01:44 - Думай как компьютер... 02:10 - Алгоритм поиска в глубину (DFS) 02:22 - Анимация поиска в глубину (DFS) 02:58 - Логика обхода графа в DFS 03:45 - Возвращаемся к анимации поиска пути от А до Б 04:37 - Что если сократить путь? 05:19 - Что если пути нет? Как DFS работает тогда? 05:32 - Какой план дальше? 05:55 - Секрет понимания графов 06:04 - Хранение графа в виде карты в памяти 06:25 - Код для проверки пути от А до Б через поиск в глубину (Python) 07:30 - Магия поиска в глубину 07:45 - Структура написания поиска в глубину (DFS) 08:07 - Понять все сразу не просто... 08:26 - Java, JavaScript, C++, Go: поиск в глубину 08:40 - Задача: раскраска по номерам 09:30 - Учимся закрашивать соседние клетки поиском в глубину 10:36 - Код для заливки соседей 11:05 - Java, JavaScript, C++, Go: заливка соседей 11:12 - Учимся считать число заливок 12:21 - Код для подсчета заливок (Python) 12:57 - Java, JavaScript, C++, Go: подсчет компонент связности 13:10 - Проблема больших матриц... 13:33 - Основные области памяти 13:44 - Ограничения стековой области памяти 14:12 - Решаем проблему переполнения стека 14:37 - Код итеративной реализации подсчета компонент связности (Python) 15:02 - Про использование стека 15:13 - Возвращаемся к коду 15:58 - Java, JavaScript, C++, Go: итеративный подсчет компонент связности 16:09 - Важный дисклеймер 16:19 - Оценим время и памяти в Big O 17:21 - Худший случай оценки по памяти 17:25 - Типичная оценка для обхода в глубину (DFS) 17:32 - Время и память при проверке пути от А до Б 17:50 - Что от тебя ждут на собеседовании 17:57 - Рекурсивный vs итеративный обход в глубину 18:18 - Ты красавчик! 18:30 - Про практику 19:20 - Алгоритмы поиска кратчайшего пути 19:31 - Задача поиска минимального расстояния от А до Б 19:58 - Анимация поиска в ширину (BFS) 20:22 - База, чтобы написать поиск в ширину... 20:44 - Чем можно заменить очередь в поиске в ширину (BFS) 21:11 - Идея решения поиска кратчайшего расстояния от А до Б 23:15 - Код поиска в ширину (Python) 24:12 - Java, JavaScript, C++, Go: поиск в ширину 24:22 - Более подробно разбираем обход соседей клетки 24:42 - Типичная ошибка при реализации поиска в ширину 25:09 - Интересный факт про поиск в ширину 25:32 - Оцениваем поиск расстояния от А до Б в Big O 26:15 - Оцениваем максимальный размер очереди в поиске в ширину (BFS) 27:34 - Возвращаемся к оценке по памяти 27:56 - Поиск кратчайшего маршрута 28:25 - Модификация BFS для поиска маршрута 28:42 - Смотрим код (Python) 29:42 - Разбираем восстановление пути 30:45 - Java, JavaScript, C++, Go: восстановление кратчайшего пути 30:52 - Оцениваем время и память в Big O 31:32 - Чилим 32:45 - Делаем систему быстрого реагирования 33:40 - Как решить проблему множественного запуска поиска в ширину 34:30 - Реализуем Multy Source BFS (Python) 35:32 - Java, JavaScript, C++, Go: Multy Source BFS 35:43 - А точно ли Multy Source BFS нужен? 36:02 - Код альтернативного решения (Python) 36:07 - Java, JavaScript, C++, Go 36:18 - Сравниваем варианты решения 36:40 - Где использовать обход в ширину, а где в глубину (BFS vs DFS) 37:18 - Зачем нужен DFS если есть BFS 37:42 - Как решают задачи на графы на собесах 38:09 - Как я рассказываю идею решения на собеседовании 39:18 - Как усилить конкурентное преимущество 🔥 ПРАКТИКА И ПОДГОТОВКА К СОБЕСАМ: Практика по графам и подготовка к алгоритмическим собеседованиям: https://clck.ru/3RAkSo ⚠️ По ссылке доступен промокод со скидкой! Финальные условия промокода могут измениться и всегда отображаются на сайте. 📱 МОЙ TELEGRAM КАНАЛ: https://t.me/algocode_algorithms Здесь я делюсь дополнительными материалами, разборами задач и анонсами новых видео. Подписывайся! По поводу мини-групп писать в ТГ: fatinmaks Реклама. ИП Фатин. ИНН: 525406426719. Erid: 2Vtzqv9yRzv