Grundy

Интерактивное сравнение: https://grundyjs.ru/algorithms/mst-comparison/?utm_source=rutube&utm_medium=social&utm_campaign=mst_comparison&utm_content=vertical Сравниваем два алгоритма на одном неориентированном взвешенном графе. Прим растит одно дерево: каждый раз выбирает самое дешёвое ребро между уже присоединёнными вершинами и остальным графом. Краскал рассматривает рёбра всего графа по возрастанию веса и соединяет разные компоненты, пропуская циклы. Прим от A выбирает A—C = 2, C—B = 1, C—E = 5 и E—D = 2. Краскал выбирает B—C = 1, A—C = 2, D—E = 2 и C—E = 5; A—B = 4 пропускает, поскольку его концы уже соединены через C. После третьего принятого ребра у Прима сумма 8, у Краскала — 5. Это промежуточные состояния: в конце оба получают четыре ребра и общую стоимость 10. Синий — Прим, зелёный — Краскал. Общие рёбра показаны параллельными цветными линиями. Краскал временно строит несколько отдельных деревьев. Это сравнение порядка выбора, а не замер скорости: синхронные фазы анимации не равны времени работы алгоритмов. Минимальный остов всей сети и кратчайшие пути от старта — разные задачи. В интерактивном примере можно менять граф, веса и старт Прима, проходить сравнение по шагам, поделиться ссылкой на свой граф и сохранить анимацию. Нулевые и отрицательные веса допустимы; в несвязном графе оба алгоритма строят минимальный остовный лес. Авторская озвучка, без музыки. #алгоритмы #Прим #Краскал #графы #программирование

Интерактивный разбор: https://grundyjs.ru/algorithms/kruskal/?utm_source=rutube&utm_medium=social&utm_campaign=kruskal&utm_content=vertical Алгоритм Краскала строит минимальное остовное дерево неориентированного взвешенного графа: соединяет все вершины без циклов с минимальной суммой весов рёбер. Сортируем рёбра всего графа по весу. Если концы ребра находятся в разных компонентах — берём ребро и объединяем их. Если вершины уже связаны — пропускаем ребро, чтобы не создать цикл. На этом графе выбираются B—C = 1, A—C = 2, D—E = 2 и C—E = 5. Ребро A—B = 4 пропускаем: его концы уже связаны через C. Получается четыре ребра с общей стоимостью 10. Как только все вершины соединены, остальные рёбра проверять не нужно. У Прима на том же графе та же сумма, но другой порядок выбора. Минимальная стоимость всей сети и кратчайшие пути от старта — разные задачи. Нулевые и отрицательные веса допустимы. При B—C = −3 и D—E = 0 сумма становится 4. В несвязном графе получаем минимальный остовный лес: в примере два дерева, три ребра и общая сумма 5. В интерактивном примере можно менять веса, проходить алгоритм по шагам, поделиться своим графом и сохранить анимацию. Зелёный — выбранный остов, жёлтый — текущее ребро, пунктир — пропущенное ребро цикла. Группы под графом показывают компоненты, список справа — порядок рёбер. Авторская озвучка, без музыки. #алгоритмы #Краскал #графы #деревья #программирование

Интерактивный разбор: https://grundyjs.ru/algorithms/prim/?utm_source=rutube&utm_medium=social&utm_campaign=prim&utm_content=vertical Алгоритм Прима строит минимальное остовное дерево неориентированного взвешенного графа: соединяет все вершины без циклов с минимальной суммой весов рёбер. На каждом шаге выбираем самое лёгкое ребро на всей границе уже построенного дерева — из включённой вершины в ещё не включённую. На этом графе выбираются A—C = 2, C—B = 1, C—E = 5 и E—D = 2. Получается четыре ребра с общей стоимостью 10. После добавления B следующее ребро выходит из более ранней C: сравниваем всю границу, а не только последнюю вершину. Это минимум стоимости всей сети; кратчайшие пути от старта — другая задача. Нулевые и отрицательные веса допустимы. При B—C = −3 и D—E = 0 сумма становится 4. Если убрать связи между группами A,B,C и D,E, Прим построит минимальный остовный лес: два дерева, три ребра и общая сумма 5. В интерактивном примере можно менять веса и старт, проходить алгоритм по шагам, поделиться своим графом и сохранить анимацию. Синий пунктир показывает все рёбра границы одновременно, жёлтый — выбранный минимум, зелёный — остов. Авторская озвучка, без музыки. #алгоритмы #Прим #графы #деревья #программирование

Интерактивное сравнение: https://grundyjs.ru/algorithms/shortest-path-comparison/?utm_source=rutube&utm_medium=social&utm_campaign=shortest_path_comparison&utm_content=vertical На одном ориентированном графе сравниваем три алгоритма. Дейкстра закрепляет вершину с наименьшей известной стоимостью от старта и требует неотрицательных весов. Беллман — Форд повторяет полные проходы по рёбрам; он допускает отрицательные веса. Оба вычисляют расстояния от одного источника. Флойд — Уоршелл разрешает промежуточные вершины по очереди и вычисляет матрицу расстояний между всеми парами. Для сравнения берём её строку A. На исходных весах все три находят путь A → B → C → D: 3 + 2 + 2 = 7. После изменения B → C на −2 стоимость становится 3. Дейкстру в этом режиме не запускаем; Беллман — Форд и Флойд — Уоршелл продолжают работать. Добавляем C → B веса 1: цикл B → C → B стоит −1. Повторяя его, можно удешевлять путь из A в D сколько угодно — конечного минимума нет (−∞). Но D → D остаётся 0: от D этот цикл недостижим. Обратного пути D → A нет (∞). При единичных весах минимальная стоимость совпадает с минимальным числом рёбер: прямое ребро A → D даёт стоимость 1. Такты анимации показывают этапы алгоритмов, а не замер быстродействия. В интерактивном примере можно менять веса, источник и цель, сравнивать этапы и поделиться ссылкой на свой граф. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #Дейкстра #БеллманФорд #ФлойдУоршелл #графы #программирование

Интерактивный разбор Флойда — Уоршелла: https://grundyjs.ru/algorithms/floyd-warshall/?utm_source=rutube&utm_medium=social&utm_campaign=floyd_warshall&utm_content=vertical Флойд — Уоршелл находит минимальную стоимость путей сразу между всеми парами вершин. В матрице строка задаёт начало, столбец — конец. На каждом этапе разрешаем ещё одну промежуточную вершину k и проверяем d(i,j) = min(d(i,j), d(i,k) + d(k,j)). В примере прямой путь A → D стоит 10. Через B получается 3 + 6 = 9. Через C — маршрут A → B → C → D стоимостью 3 + (−2) + 2 = 3. Ячейки одного этапа обновляются вместе из предыдущего слоя матрицы. Обратного пути D → A здесь нет: ∞ означает недостижимость. Если все веса равны единице, минимальная стоимость совпадает с минимальным числом рёбер. В этом примере прямое ребро A → D тогда даёт стоимость 1. Отрицательные рёбра допустимы. Отрицательное число на диагонали после основных этапов указывает на отрицательный цикл. Цикл B → C → B стоит −2 + 1 = −1. Для пар, чей маршрут может пройти через такой цикл, конечного минимума нет: −∞. Остальные ответы сохраняются. Время O(V³), матрицы расстояний и восстановления маршрутов занимают O(V²). В интерактивном примере можно менять веса, выбирать пару вершин и смотреть этапы алгоритма, а также поделиться ссылкой на свой граф. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #ФлойдУоршелл #графы #программирование

Интерактивный разбор Беллмана — Форда: https://grundyjs.ru/algorithms/bellman-ford/?utm_source=rutube&utm_medium=social&utm_campaign=bellman_ford&utm_content=vertical Беллман — Форд ищет минимальную стоимость пути в ориентированном графе, в том числе с отрицательными весами. На каждом проходе проверяет все рёбра: если d(u) + вес меньше d(v), обновляет расстояние и предка. В исходном примере четыре вершины и три основных прохода. После первого прохода d(A) = 2, d(B) = 5. Во втором цель сначала получает оценку 4, а отрицательное ребро B → A улучшает A до 1. На третьем проходе стоимость до цели уменьшается до 3. Итоговый путь S → B → A → G: 5 − 4 + 2 = 3. После основных проходов выполняется отдельная контрольная проверка. Если достижимую оценку всё ещё можно улучшить, есть отрицательный цикл, достижимый от старта. Добавим A → B с весом 3: цикл A → B → A стоит 3 − 4 = −1. Каждый круг уменьшает стоимость. Из цикла можно попасть в G, поэтому для цели нет конечного минимума: d(G) = −∞. Недостижимый от старта цикл X ↔ Y на ответ не влияет: путь к G по-прежнему стоит 3. Отрицательное ребро само по себе не означает отрицательного цикла. Если достижимый цикл не ведёт к выбранной цели, стоимость до этой цели может оставаться конечной. На первой найденной оценке цели останавливать алгоритм нельзя. В интерактивном разборе можно пройти алгоритм по шагам, изменить вес ребра, выбрать старт и цель, сравнить пять примеров и поделиться своим графом. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #БеллманФорд #графы #программирование

Интерактивное сравнение BFS, Дейкстры и A*: https://grundyjs.ru/algorithms/weighted-maze-search/?utm_source=rutube&utm_medium=social&utm_campaign=weighted_maze_search&utm_content=vertical Один взвешенный лабиринт, одинаковые старт и выход — три правила выбора следующей клетки. Синий BFS ищет минимум по числу переходов и не учитывает цену клеток. Жёлтый алгоритм Дейкстры выбирает минимальную известную стоимость от старта. Фиолетовый A* добавляет к ней оценку оставшегося пути: расстояние по горизонтали и вертикали без учёта стен, умноженное на минимальную цену шага. Результаты исходной карты: • BFS: 16 переходов, стоимость 22, обработано 76 клеток. • Дейкстра: 18 переходов, стоимость 18, обработано 62 клетки. • A*: 18 переходов, стоимость 18, обработана 31 клетка. Больше переходов, зато дешевле. При единичных весах стоимость равна числу переходов: все три поиска находят путь из 16 переходов стоимостью 16. Ветви одной волны показаны одновременно, исчерпанные тупики сереют. У алгоритмов разные приоритеты; длительность анимации не измеряет быстродействие программы. На другой карте преимущество A* по числу обработанных клеток может измениться. В интерактивном разборе меняйте цену клетки, проходите поиск по шагам и сравнивайте результаты. Авторская озвучка. Музыки нет. #алгоритмы #BFS #Дейкстра #AStar #программирование

Интерактивный разбор алгоритма Дейкстры: https://grundyjs.ru/algorithms/dijkstra/?utm_source=rutube&utm_medium=social&utm_campaign=dijkstra&utm_content=vertical Дейкстра выбирает вершину с минимальной известной стоимостью пути от старта. При проверке соседей складывает текущую стоимость с весом ребра и, если путь дешевле, обновляет расстояние и предка. На этом графе BFS нашёл бы S → A → G: два перехода, но цена 8 + 1 = 9. Дейкстра находит S → B → C → G: три перехода с ценой 1 + 1 + 2 = 4. По ходу поиска стоимость до A уменьшается с 8 до 4 через B. Если все веса равны единице, стоимость пути равна числу рёбер: минимальная стоимость и минимальное число переходов совпадают. Дейкстра гарантирует минимальную стоимость при неотрицательных весах. Останавливаем поиск при извлечении цели из границы, а не при её первом обнаружении. В интерактивном разборе можно пройти поиск по шагам, переключить веса на единицу, изолировать цель или совместить её со стартом. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #Дейкстра #графы #программирование

Посмотрите A* по шагам на сайте: https://grundyjs.ru/algorithms/a-star-search/?utm_source=rutube&utm_medium=social&utm_campaign=a_star_search&utm_content=vertical A* выбирает клетку с минимальным f = g + h. g — длина лучшего пока найденного пути от старта, h — манхэттенская оценка до цели без учёта стен. На том же лабиринте 7 × 4 жадный поиск находит маршрут из 10 переходов, а A* — из 8. В ролике разбираем выбор из всей границы поиска, тупик рядом с выходом и восстановление пути по предкам. В этой сетке движения разрешены по четырём направлениям и каждый проход стоит единицу. Манхэттенская эвристика согласованна, поэтому A* гарантирует кратчайший путь. На сайте можно пройти алгоритм по шагам, менять скорость и проверить случай, когда старт совпадает с целью. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #лабиринт #AStar #программирование

Посмотрите жадный поиск по шагам на сайте: https://grundyjs.ru/algorithms/greedy-best-first-search/?utm_source=rutube&utm_medium=social&utm_campaign=greedy_best_first_search&utm_content=vertical Жадный поиск (Greedy Best-First Search) выбирает среди обнаруженных клеток ту, у которой наименьшая оценка расстояния до выхода. В примере используется манхэттенское расстояние: сколько переходов понадобилось бы без стен. На сетке 7 × 4 сначала попадаем в тупик рядом с выходом, затем находим верхний обход. Путь по сохранённым предкам содержит 10 переходов, хотя снизу можно пройти за 8. Жадный поиск не учитывает уже пройденное расстояние и не гарантирует кратчайший путь. На сайте можно пройти алгоритм по шагам, менять скорость и сравнить обычный пример со случаем, когда старт совпадает с целью. Авторская озвучка, без музыки. Русские субтитры подготовлены отдельной дорожкой. #алгоритмы #лабиринт #GreedyBestFirst #программирование

Перенесите старт и сравните BFS и DFS на сайте: https://grundyjs.ru/algorithms/maze/?utm_source=rutube&utm_medium=social&utm_campaign=maze&utm_content=search_vertical Сравниваем поиск в ширину (BFS) и поиск в глубину (DFS) на одном лабиринте. BFS использует очередь и распространяется по слоям расстояния; DFS идёт по ветке и возвращается из тупиков по стеку. Найденный маршрут восстанавливается по родителям клеток. В примере — сетка 7 × 5, seed 34: от старта (1, 1) до выхода (7, 5) оба метода находят путь из 14 переходов. Здесь нет циклов, поэтому простой путь единственный. BFS сделал текущими 19 клеток, DFS — 27; это числа активированных клеток в данном примере, а не универсальное сравнение скорости алгоритмов. Если есть циклы, DFS может найти более длинный путь. BFS гарантирует кратчайший маршрут по числу переходов, когда каждый переход имеет одинаковую стоимость. В загруженном лабиринте выход может быть недостижим. Перенесите старт или выход, измените seed, управляйте шагами и сравните обходы. Можно сохранить лабиринт в JSON или загрузить свой. Авторская озвучка, без музыки. Сцена использует модель и плеер сайта; MP4 со звуком записаны напрямую через CanvasTake. Русские субтитры подготовлены отдельной дорожкой. Как построен этот лабиринт: https://rutube.ru/video/c4095f82edb36b2ff6d04382eaaf7570/ #алгоритмы #лабиринт #BFS #DFS #программирование

Постройте свой лабиринт: https://grundyjs.ru/algorithms/maze/?utm_source=rutube&utm_medium=social&utm_campaign=maze&utm_content=generation_vertical Меняйте seed, делайте шаги вперёд и назад и наблюдайте за стеком. Рандомизированный поиск в глубину (DFS) строит лабиринт: выбираем ещё не посещённого соседа, открываем проход и сохраняем текущую ветку в стеке. В тупике возвращаемся до клетки с неисследованным направлением. В примере — сетка 7 × 5, seed 34: 35 клеток и 34 прохода. Каждый новый проход ведёт в новую клетку, поэтому циклов нет. После обхода всей сетки получается связное дерево: между любыми двумя клетками, в том числе выбранными стартом и выходом, есть единственный простой путь. Попробуйте другой seed, управляйте шагами и сравните получившиеся лабиринты. Поиск пути через BFS и DFS — отдельная тема; этот ролик посвящён генерации. Авторская озвучка, без музыки. Запись canvas со звуком — CanvasTake. #алгоритмы #лабиринт #DFS #программирование

Меняйте старт и цель в интерактивном DFS: https://grundyjs.ru/algorithms/depth-first-search/?utm_source=rutube&utm_medium=social&utm_campaign=depth_first_search&utm_content=vertical Управляйте шагами, проследите за стеком и сравните с поиском в ширину. Поиск в глубину (DFS) идёт по одной ветке, хранит активные вызовы в стеке и возвращается назад, когда новые соседи заканчиваются. В этом графе путь из A до F — A → B → D → G → E → C → F: 6 рёбер. Но есть путь A → C → F — всего 2 ребра. DFS находит путь, но не гарантирует кратчайший. BFS находит кратчайший путь по числу рёбер в невзвешенном графе. Показываем полный обход достижимой компоненты, возвраты и восстановление пути по предкам. Вершина H недостижима из A. Для списка смежности время — O(V + E), дополнительная память самого алгоритма — O(V), без снимков истории визуализации. Озвучка автора, без музыки. Визуализация — AlgiViz, запись со звуком — CanvasTake. #алгоритмы #DFS #поисквглубину #программирование

Попробуйте BFS и посмотрите код: https://grundyjs.ru/algorithms/breadth-first-search/?utm_source=rutube&utm_medium=social&utm_campaign=breadth_first_search&utm_content=vertical Выберите старт и цель, управляйте шагами и проследите за очередью. Как очередь помогает найти кратчайший путь в невзвешенном графе? Показываем поиск в ширину (BFS) шаг за шагом: открытие вершин, очередь, расстояния и восстановление пути по родителям. В примере путь из A в G — A → B → D → G: три ребра. Вершина H недостижима из A. Обходим всю достижимую компоненту, затем восстанавливаем один из кратчайших путей. BFS минимизирует число рёбер: все переходы имеют одинаковую стоимость. Для списка смежности время — O(V + E), дополнительная память самого алгоритма — O(V), без истории визуализации. Озвучка автора, без музыки. Визуализация — AlgiViz, запись со звуком — CanvasTake. #алгоритмы #поисквширину #BFS #программирование

Проверь массив из шести чисел: https://grundyjs.ru/algorithms/selection-sort/?utm_source=rutube&utm_medium=social&utm_campaign=selection_sort&utm_content=sorted_comparisons_vertical Введи 1, 2, 3, 4, 5, 6, нажми «Применить», затем «Старт» и посмотри на счётчик сравнений. Массив уже отсортирован, но сортировка выбором всё равно ищет минимум на каждом проходе. Для пяти чисел получается десять сравнений и ни одного обмена. А сколько будет для шести? Авторская озвучка. Визуализация — AlgiViz, запись видео со звуком — CanvasTake. #алгоритмы #сортировка #программирование

Как найти число, не перебирая весь массив? Бинарный поиск каждый раз отбрасывает половину оставшегося диапазона. Находим первую шестёрку среди повторов, затем ищем отсутствующую семёрку. В каждом из этих примеров достаточно четырёх проверок среднего элемента из шестнадцати. Попробовать на своём массиве и посмотреть код: https://grundyjs.ru/algorithms/binary-search/?utm_source=rutube&utm_medium=social&utm_campaign=binary_search&utm_content=vertical Массив должен быть отсортирован заранее. Показанный вариант возвращает первое вхождение: даже после совпадения поиск продолжается слева. Время поиска — O(log n), дополнительная память самого алгоритма — O(1). Озвучка автора. Визуализация — AlgiViz, запись видео со звуком — CanvasTake. #бинарныйпоиск #алгоритмы #binarysearch

Две одинаковые двойки — фиолетовая и голубая. Один обмен с минимумом меняет их взаимный порядок. Так выглядит неустойчивость сортировки выбором. Попробуйте свой массив: https://grundyjs.ru/algorithms/selection-sort/?utm_source=rutube&utm_medium=social&utm_campaign=selection_sort&utm_content=instability_experiment_vertical Авторская озвучка. Визуализация — AlgiViz, запись — CanvasTake. #алгоритмы #сортировка #программирование

Heap sort по шагам: строим максимальную кучу, извлекаем максимум и просеиваем новый корень. Интерактивный разбор и код: https://grundyjs.ru/algorithms/heap-sort/?utm_source=rutube&utm_medium=social&utm_campaign=heap_sort&utm_content=vertical Построение O(n), худшее время O(n log n). Итеративный алгоритм на месте требует O(1) дополнительной памяти, без учёта копии входа и истории визуализации. Сортировка неустойчива. Визуализация: AlgiViz. Запись MP4: CanvasTake. Без звука. #алгоритмы #сортировка #heapsort #AlgiViz

Трёхстороннее разбиение — Quick sort по шагам. Группируем значения меньше, равные и больше опорного. После обмена справа проверяем пришедший элемент; рекурсия пропускает равную область. Интерактивный разбор и код обоих вариантов: https://grundyjs.ru/algorithms/quick-sort/?utm_source=rutube&utm_medium=social&utm_campaign=quick_sort&utm_content=three_way_vertical В среднем на случайных перестановках различных значений — Θ(n log n), в худшем случае — Θ(n²). Оба варианта нестабильны. Визуализация: AlgiViz. Запись: CanvasTake. Видео без звука. Русские субтитры доступны отдельной дорожкой на YouTube. #алгоритмы #сортировка #quicksort #AlgiViz

Разбиение Ломуто — Quick sort по шагам. Берём последний элемент опорным, переносим меньшие значения влево и ставим опорный на окончательную позицию. Интерактивный разбор и код обоих вариантов: https://grundyjs.ru/algorithms/quick-sort/?utm_source=rutube&utm_medium=social&utm_campaign=quick_sort&utm_content=lomuto_vertical В среднем на случайных перестановках различных значений — Θ(n log n), в худшем случае — Θ(n²). Оба варианта нестабильны. Визуализация: AlgiViz. Запись: CanvasTake. Видео без звука. Русские субтитры доступны отдельной дорожкой на YouTube. #алгоритмы #сортировка #quicksort #AlgiViz