MST Prim для представления списка смежности - PullRequest
0 голосов
/ 09 мая 2020

Я пытался реализовать алгоритм Прима, используя min Heap. вот ссылка, которую я имел в виду https://www.geeksforgeeks.org/prims-mst-for-adjacency-list-representation-greedy-algo-6/

Мне было интересно, почему мы можем использовать вектор и сортировать его с помощью функции std::sort вместо минимальной кучи.

1 Ответ

0 голосов
/ 09 мая 2020

Вы могли бы, но помните, что каждый раз, когда новый узел добавляется в MST, вы должны обновлять набор ребер, которые пересекают раздел (ребра до узлов, которых еще нет в MST), поэтому вам придется отсортировать ваш вектор на каждой итерации алгоритма, что приведет к потере времени, поскольку вам просто нужно знать, какое из ребер, пересекающих раздел, имеет минимальное значение на этой итерации, минимальная куча оптимальна для этой операции, так как ее временная сложность для при извлечении минимального значения O(log n) при сортировке O(n log n) алгоритм может работать медленнее на больших или плотных графах.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...