[prev] [index] [next]

Prim's Algorithm

Another approach to computing MST for graph G(V,E):
  • start from any vertex s and empty MST
  • choose edge not already in MST to add to MST
    • must not involve a self-loop
    • must connect to a vertex already on MST
    • must have minimal weight of all such edges
  • repeat until MST covers all vertices
Critical operations:
  • checking for vertex being connected in a graph
  • finding min weight edge in a set of edges