[prev] 55 [next]

Prim's Algorithm (cont)

Rough time complexity analysis …
  • V iterations of outer loop
  • in each iteration …
    • find min edge with set of edges is O(E) ⇒ O(V·E) overall
    • find min edge with priority queue is O(log E) ⇒ O(V·log E) overall