Comments 22
Круто !
а зачем здесь нужна очередь с приоритетом?
Приоритетная очередь нужна для поиска соседа для текущей вершины с минимальным весом. Она устроена так, что из нее извлекаются элементы с минимальным весом первыми.
кажется, что такое можно делать и при помощи массива. просто перебирать все вершины и брать ту, которая соседняя и с минимальным текущим расстоянием. очередь с приоритетом выглядит как менее очевидное решение
Проблема вашего предложения кроется в словосочетании "перебирать все". Да, так можно, но это долго по времени
так у Вас граф в матрице смежности хранится. Вы при каждом извлечении из очереди всё равно все вершины перебираете
Я конечно может что то не так понял в статье, детально ее изучать не стал, просто бегло просмотрел. Но в классическом Приме в priority queue добавляются вершины, при очередном добавлении вершины в остовное дерево, по моему у автора тоже такая реализация. Примерно происходит следующее:
Добавляем в остов первую любую вершину, и всех ее соседей.
Из priority queue достаём минимальную
Добавляем ее в остов
Проходимся по соседям добавленной в остов вершины, и кладём их в очередь.
Если в остов входят не все вершины, то возвращаемся к шагу 2
При таком подходе, будет в худшем случае m добавлений в priority queue, где m — количество ребер. Что дает асимптотику m*log m или m*log n, в зависимости от реализации. Против вашей n * m. Даже при плохой реализации с priority queue, ваш вариант выгоден только при n < log m, то есть на очень плотных графах
Что дает асимптотику m*log m или m*log n, в зависимости от реализации
хорошо, тогда в авторской реализации получается, что для каждого элемента из очереди автор будет перебирать все вершины графа, чтобы перейти куда-то по ребру, поэтому у автора будет не лучше, чем O(n * m)
Против вашей n * m
откуда m? я думаю, что это n²: добавляю в остов по одной вершине, перебирая все n и выбирая ту, которая смежная с уже выбранной и инцидентна минимальному ребру. итого размер остова * n = n²
для каждого элемента из очереди вы будете перебирать все вершины графа
Почему, нет. Извлечение из очереди работает за O(1), а добавление за O(размер очереди), то есть O(log m)/O(log n) в зависимости от реализации. Суммарно мы добавим в очередь m раз (так как ребер m, и мы каждое ребро обработаем не больше одного раза). Извлечем n раз, так как остов размера n, извлечение O(1), поэтому итого O(n), итого весь алгоритм O(m * log m + n), где n по правилам асимптотики можно опустить, если считать, что m примерно равно n, а это вероятно так, для задачи остова.
откуда m? я думаю, что это n²
На каждом шаге (а таких шагов у вас будет n, так как вы будете добавлять в остов по одной вершине), вы должны перебрать ВСЕ ребра. Как вы собрались за O(1) определить для каждой вершины минимальное ребро (при этом, которое не входит в остов, что важно)? Магия?
P.S.: Алгоритм Прима за O(nˆ2) действительно существует, но по вашим комментариям, мне показалось, что вы говорите не о нем, и опять же, алгоритм за O(nˆ2), хорош для плотных графов. На разреженных графах он будет проигрывать варианту с приоритетной очередью
Извлечение из очереди работает за O(1)
неправда, логарифм размера.
добавление за O(размер очереди)
неправда, логарифм размера.
Суммарно мы добавим в очередь m раз
Извлечем n раз
так, ну так быть не может. извлекать Вы будете столько, сколько положили. log m и log n возникают из-за того, умеем ли мы менять элементы в очереди. если не умеем, то нам придётся хранить в очереди невалидные данные, и, когда мы будем невалидную вершину из очереди брать, мы можем за O(1) понять что она невалидная и просто выбросить эту вершину. тогда у нас получается, что в очереди будут находиться m элементов, и мы все из них извлечём за O(m * log(m)) суммарно. если умеем менять элементы в очереди, то такой проблемы не будет, и тогда размер очереди будет n и извлекать мы будем n элементов за O(n * log(n)) суммарно
итого весь алгоритм O(m * log m + n)
Вы никак не учли перебор соседних вершин, квадрат возникает там
По поводу извлечения, да, перепутал с просмотром, вы правы, за log размера, но это не влияет на асимптотику, в итоге все равно O(m*log m).
По поводу добавления просто опечатка, конечно за log размера, что вообще-то даже меньше чем за размер кучи.
Вы никак не учли перебор соседних вершин, квадрат возникает там
Вот здесь уже вы не правы, там нигде не возникает квадратов. Перебор соседних вершин на каждом шаге учтен амортизировано. То есть я говорю, что суммарно мы положим в очередь m раз, потому что всего ребер m, а на каждом шаге мы перебираем только соседей, а не все ребра, если у автора матрица смежности, а не список смежности, это другой вопрос, я не вникал в детали, и говорю про классического Прима.
Про извлечение вершин - да, хорошо, нужно извлечь все, ну и что? Это не влияет на асимптотику, она все равно O(m * log m), или O(m * log n), если как вы говорите, научиться обновлять элемент, а не добавлять новый, а это можно сделать, если например использовать бинарное дерево, которое по асимптотике дает все тоже самое, только бонусом умеет обновлять элемент (тоже за log)
P.S.: посмотрел, у автора действительно матрица смежности, но это проблема автора, а не алгоритма. Вы могли указать на это, а не предлагать вообще другой вариант, подходящий для плотных графов.
Уточню: в статье идет перебор не всех ребер, а только исходящих из добавляемой в остов вершины, то есть соседей. В вашей версии без priority_queue, вы не можете делать тоже самое, т. к. не факт, что следующая вершина на добавление в остов, будет лежать среди соседей добавляемой. На каждом шаге вам нужно либо перебирать ВСЕ вершины, либо иметь под рукой priority_queue, который любезно расскажет, у какой вершины минимальное ребро, из текущего остова
если хранить граф в виде матрицы смежности, то перебор всех соседей и перебор всех вершин — это одно и то же. а с массивом можно делать так: давайте заведём массив, где для каждой вершины будем хранить вес минимального ребра, которое инцидентно данной вершине и какой-то вершине из остова, изначально там все значения равны бесконечности. будем постепенно добавлять вершины в остов. первой может быть любая. возьмём какую-нибудь, переберём все вершины, если очередная смежна выбранной, то обновим минимальный вес инцидентного ребра. дальше переберём все вершины, выберем среди не посещённых вершину с минимальным весом инцидентного ребра, обновим инцидентные ей рёбра и так далее до тех пор, пока все вершины в остове не окажутся. вполне честный прим за O(n²)
Это как раз и есть тот самый Прим за квадрат, но хочу заметить, что ваш изначальный комментарий был про то, что проще обойтись массивом (приоритетная очередь менее очевидное решение, как вы писали), но ваш вариант с поддержкой минимальных ребер не проще, а может быть даже сложнее. И еще раз повторюсь, он хорош только для плотных графов, для разреженных, очередь с приоритетом лучший выбор
ну не знаю, мне кажется, что эти алгоритмы сами по себе примерно одинаковой очевидности, но для варианта с кучей нужно использовать достаточно сложную с точки зрения внутреннего устройства структуру данных, поэтому квадратный вариант с точки зрения простоты (и реализации в случае отсутствия встроенной кучи в языке) мне кажется более предпочтительным. а ещё я подозреваю, что куча на матрице смежности работает медленнее, чем массив на матрице смежности, но да, изначально я об этом не писал, потому что хотел понять, почему автор привёл именно такое решение
Ну, сами видите, более очевидным его назвать точно нельзя, ну а приоритетные очереди и деревья обычно уже реализованы в стандартных библиотеках языков, то что автор реализует это вручную, проблема языка, если там такого нету. + Вариант с приоритетной очередью кмк более популярен, и чаще встречается во всяких задачах итд, т.к. графы чаще разреженные, чем плотные, имхо
Во времена моего программистского детства почти 40 лет назад мы обычно не знали названий конкретных алгоритмов поиска пути, но знали две группы алгоритмов -- "поиск вглубь" (хороший пример -- рекурсивные алгоритмы), при котором ты просматривает путь сначала вглубь, потом вариации, и "поиск вширь", при котором идёшь от одной вершины и подсчитываешь цену пути от начала до набора просматриваемых в данный момент точек. Именно ко второй группе относится Ваш алгоритм.
Дальше на основе общей идеи этих групп можно конструировать алгоритмы под конкретную задачу, часто с серьёзными вариациями (например, для конкретной задачи часто нужен необычный порядок выборки вершины из набора просматриваемых). Остаётся прикинуть в каждом случае две основных характеристики алгоритма -- вычислительную сложность и (сейчас это реже надо смотреть) используемую память. Иногда -- для среднего и худшего случая отдельно. Вообще это всё очень забавный конструктор алгоритмов, в который раньше постоянно играли в олимпиадных задачах.
Алгоритм Прима