Я обнаружил, что there are two ways to implement Prim algorithm и что временная сложность с матрицей смежности равна O (V^2), а временная сложность с списком кучи и смежности равна O (E lg (V)).Может ли реализация матрицы смежности Prim использовать минимальную кучу?
Мне интересно, могу ли я использовать кучу, когда граф представлен матрицей смежности. Имеет ли это смысл? Если да, есть ли разница между матрицей смежности + кучей и списком смежности + кучей?
Как правило, матричное представление-граф не так хорошо подходит для алгоритма Prim.
Это из-за основной итерации алгоритма, который выталкивает узел из кучи, а затем сканирует его соседей. Как вы находите своих соседей? Используя представление матричного графа, вам в основном нужно перебрать всю строку матрицы (в графическом представлении списка вам просто нужно зациклиться на списке узлов, что может быть значительно короче).
Это означает, что, независимо от кучи, просто суммы части нахождения соседа из хлопнутого узла уже Ω (| V |), так как строка каждого узла, в конечном счете сканироваться.
Итак, нет - это не имеет большого смысла. Куча не снижает общую сложность.
О, да! Цикл реализации Prim похож на BFS. При реализации с использованием списка смежности BFS принимает O (V + E), используя матрицу, она принимает O (V^2). У меня появилась идея. – Jayce