Вариант с приоритетной очередью кмк более популярен, и чаще встречается во всяких задачах
но по факту графы всё равно разные бывают, так что по-хорошему указывать, для какого именно случая решается задача, и выбирать алгоритм уже исходя из этого)
ну не знаю, мне кажется, что эти алгоритмы сами по себе примерно одинаковой очевидности, но для варианта с кучей нужно использовать достаточно сложную с точки зрения внутреннего устройства структуру данных, поэтому квадратный вариант с точки зрения простоты (и реализации в случае отсутствия встроенной кучи в языке) мне кажется более предпочтительным. а ещё я подозреваю, что куча на матрице смежности работает медленнее, чем массив на матрице смежности, но да, изначально я об этом не писал, потому что хотел понять, почему автор привёл именно такое решение
ну может автору наоборот на плотных графах надо, в статье я не нашёл никакой информации о том какие там конкретно графы нужны и по какой причине там матрица смежности
а так да прошу прощения если произошло недопонимание, к Вам и алгоритму для разреженных графов вопросов не имею
так, ну так быть не может. извлекать Вы будете столько, сколько положили. log m и log n возникают из-за того, умеем ли мы менять элементы в очереди. если не умеем, то нам придётся хранить в очереди невалидные данные, и, когда мы будем невалидную вершину из очереди брать, мы можем за O(1) понять что она невалидная и просто выбросить эту вершину. тогда у нас получается, что в очереди будут находиться m элементов, и мы все из них извлечём за O(m * log(m)) суммарно. если умеем менять элементы в очереди, то такой проблемы не будет, и тогда размер очереди будет n и извлекать мы будем n элементов за O(n * log(n)) суммарно
итого весь алгоритм O(m * log m + n)
Вы никак не учли перебор соседних вершин, квадрат возникает там
если хранить граф в виде матрицы смежности, то перебор всех соседей и перебор всех вершин — это одно и то же. а с массивом можно делать так: давайте заведём массив, где для каждой вершины будем хранить вес минимального ребра, которое инцидентно данной вершине и какой-то вершине из остова, изначально там все значения равны бесконечности. будем постепенно добавлять вершины в остов. первой может быть любая. возьмём какую-нибудь, переберём все вершины, если очередная смежна выбранной, то обновим минимальный вес инцидентного ребра. дальше переберём все вершины, выберем среди не посещённых вершину с минимальным весом инцидентного ребра, обновим инцидентные ей рёбра и так далее до тех пор, пока все вершины в остове не окажутся. вполне честный прим за O(n²)
Что дает асимптотику m*log m или m*log n, в зависимости от реализации
хорошо, тогда в авторской реализации получается, что для каждого элемента из очереди автор будет перебирать все вершины графа, чтобы перейти куда-то по ребру, поэтому у автора будет не лучше, чем O(n * m)
Против вашей n * m
откуда m? я думаю, что это n²: добавляю в остов по одной вершине, перебирая все n и выбирая ту, которая смежная с уже выбранной и инцидентна минимальному ребру. итого размер остова * n = n²
кажется, что такое можно делать и при помощи массива. просто перебирать все вершины и брать ту, которая соседняя и с минимальным текущим расстоянием. очередь с приоритетом выглядит как менее очевидное решение
мне кажется, что Вы путаете подсчëт числа операций с асимптотическим анализом
такая реализация сортировки Хоара на специально подобранных данных будет иметь асимптотику O(n²)
но по факту графы всё равно разные бывают, так что по-хорошему указывать, для какого именно случая решается задача, и выбирать алгоритм уже исходя из этого)
ну не знаю, мне кажется, что эти алгоритмы сами по себе примерно одинаковой очевидности, но для варианта с кучей нужно использовать достаточно сложную с точки зрения внутреннего устройства структуру данных, поэтому квадратный вариант с точки зрения простоты (и реализации в случае отсутствия встроенной кучи в языке) мне кажется более предпочтительным. а ещё я подозреваю, что куча на матрице смежности работает медленнее, чем массив на матрице смежности, но да, изначально я об этом не писал, потому что хотел понять, почему автор привёл именно такое решение
ну может автору наоборот на плотных графах надо, в статье я не нашёл никакой информации о том какие там конкретно графы нужны и по какой причине там матрица смежности
а так да прошу прощения если произошло недопонимание, к Вам и алгоритму для разреженных графов вопросов не имею
неправда, логарифм размера.
неправда, логарифм размера.
так, ну так быть не может. извлекать Вы будете столько, сколько положили. log m и log n возникают из-за того, умеем ли мы менять элементы в очереди. если не умеем, то нам придётся хранить в очереди невалидные данные, и, когда мы будем невалидную вершину из очереди брать, мы можем за O(1) понять что она невалидная и просто выбросить эту вершину. тогда у нас получается, что в очереди будут находиться m элементов, и мы все из них извлечём за O(m * log(m)) суммарно. если умеем менять элементы в очереди, то такой проблемы не будет, и тогда размер очереди будет n и извлекать мы будем n элементов за O(n * log(n)) суммарно
Вы никак не учли перебор соседних вершин, квадрат возникает там
если хранить граф в виде матрицы смежности, то перебор всех соседей и перебор всех вершин — это одно и то же. а с массивом можно делать так: давайте заведём массив, где для каждой вершины будем хранить вес минимального ребра, которое инцидентно данной вершине и какой-то вершине из остова, изначально там все значения равны бесконечности. будем постепенно добавлять вершины в остов. первой может быть любая. возьмём какую-нибудь, переберём все вершины, если очередная смежна выбранной, то обновим минимальный вес инцидентного ребра. дальше переберём все вершины, выберем среди не посещённых вершину с минимальным весом инцидентного ребра, обновим инцидентные ей рёбра и так далее до тех пор, пока все вершины в остове не окажутся. вполне честный прим за O(n²)
хорошо, тогда в авторской реализации получается, что для каждого элемента из очереди автор будет перебирать все вершины графа, чтобы перейти куда-то по ребру, поэтому у автора будет не лучше, чем O(n * m)
откуда m? я думаю, что это n²: добавляю в остов по одной вершине, перебирая все n и выбирая ту, которая смежная с уже выбранной и инцидентна минимальному ребру. итого размер остова * n = n²
так у Вас граф в матрице смежности хранится. Вы при каждом извлечении из очереди всё равно все вершины перебираете
кажется, что такое можно делать и при помощи массива. просто перебирать все вершины и брать ту, которая соседняя и с минимальным текущим расстоянием. очередь с приоритетом выглядит как менее очевидное решение
а зачем здесь нужна очередь с приоритетом?
pop() из очереди за линию — это как-то больно о_О
очередь спокойно пишется хоть на списках, хоть на массивах, хоть на стеках с О(1) на любую операцию в среднем
что-то не припомню я разделяйку за O(2^n). за O(n * log(n)) только в сортировке слиянием и в бпф