分析

Prim算法首先将所有的顶点插入到优先队列(二叉堆实现)中,时间开销为O(V log V)。然后decreaseKey操作将需要O(log q)的时间,q是优先队列中顶点的数目,q将会小于|V|。这个操作最多需要执行2*|E|次,在这种情况下,每一个顶点都会从优先队列中删除,图中的每一条边都会被访问两次。因此总性能是O((V+2*E)*log n)或者O((V+E)*log V)。