Комментарии 7
Формально правильно, а по сути издевательство (с)
Рассмотрим возможные улучшения Вашей версии алгоритма Краскала.
"Добавляем
i-оеребро в наше остовное дерево" - Вы не говорите, откуда у нас вообще взялось "остовное дерево" (на самом деле, некий частичный граф, который станет остовным деревом в конце алгоритма) и как оно инициализировано.Проверять каждый раз возникновение цикла - плохая идея, так что Ваш пункт 2 лучше переформулировать как-то так: "Добавляем i-ое ребро в частичный граф G', если оно соединяет две различные компоненты связности". Изначально G' не содержит ребёр, т.е. каждая вершина является отдельной компонентой связности. Можно сопоставить им номера, и корректировать их при добавлении ребра (добавляем ребро, инцидентное вершинам A и B с номерами 3 и 6 - значит, все вершины с номерами 3 и 6 получают некий новый номер, это может быть и 3, и 6, и некое f(3, 6)).
Рассматривать все рёбра графа вместо необходимого количества - это не просто детали реализации, это верный путь существенно ухудшить асимптотику. Полный граф с m вершинами содержит m*(m-1)/2 ребёр. В то время как остовное дерево любого графа с m вершинами содержит m - 1 ребро. Таким образом, очевидно, что необходимо выполнить ровно m - 1 шаг алгоритма (если рассуждать иначе - изначально есть m компонент связности и на каждом шаге две компоненты связности объединяются в одну, что уменьшает их количество на 1). Т.е. количество ребёр G' растёт с 0 до m - 1, а количество компонент связности G' уменьшается с m до 1.
В общем и целом, мне кажется, алгоритмы не сложные и на поверхностном уровне понимания "бери это, добавляй туда" всё понятно. А вот нюансы Вы не осветили в должной мере.
Здравствуйте! Учел ваш комментарий, кажется, статья стала немного лучше выглядеть :)
С 1-ым пунктом абсолютно согласен, исправил свою ошибку.
Со 2-ым пунктом тоже согласен, но вот попытка объяснить все то, что возможно на неформальном языке, кажется, провалилась :)
С 3-им пунктом согласен полностью - поправил.
Скажите, если вы изложили (наглядно!) два алгоритма, сводящихся к жадному перебору рёбер, не рассматривали ли вы возможность сравнить какие-либо характеристики (память, время, логическая сложность реализации)? Также любопытен (мне лично) аспект набора практических задач, в которых возникает необходимость находить остовное дерево (так как мне лично за многолетнюю карьеру программиста не попадалось сколь-либо близко, задача кажется довольно академичной). На лекцию "клик" не делаю, если есть возможность общения в текстовом режиме.
В части описания алгоритма Прима отсутствуют правила включения в дерево вершин вида F (см. пример). А в разборе конкретного примера алгоритма Прима про случай F предлагается догадаться. В начале написано - "что вы после прочтения данной статьи, примерно понимали, как работают жадные алгоритмы нахождения MST". У меня не получилось. Мне кажется цель статьи не достигнута и второй алгоритм "не разжеван".
Алгоритм Краскала, Прима для нахождения минимального остовного дерева