[prev] 48 [next]

Prim's Algorithm

Another approach to computing MST for graph G=(V,E):

  1. start from any vertex v and empty MST
  2. choose edge not already in MST to add to MST
    • must be incident on a vertex s already connected to v in MST
    • must be incident on a vertex t not already connected to v in MST
    • must have minimal weight of all such edges
  3. 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