Я обнаружил, что есть два способа реализовать алгоритм Prim, и что временная сложность с матрица смежности - O (V ^ 2), а временная сложность с кучей и списком смежности - O (E lg (V)).
Мне интересно, могу ли я использовать кучу, когда граф представлен матрицей смежности. Имеет ли это смысл? Если да, то есть ли разница между матрицей смежности + кучей и списком смежности + кучей?
Как правило, матричное графическое представление не так хорошо подходит для алгоритма Прима.
Это происходит из-за основной итерации алгоритма, который извлекает узел из кучи, а затем сканирует его соседей. Как найти его соседей? Используя представление графа матрицы, вам в основном нужно перебрать всю строку матрицы (в представлении графа списка вам просто нужно перебрать список узлов, который может быть значительно короче).
Это означает, что независимо от кучи просто сумма части нахождения соседей извлеченного узла уже равна (|V|2), так как каждая строка узла в конце концов сканируется.
Так что нет - особого смысла нет. Куча не уменьшает общую сложность.
