Prim's Algorithm
Another approach to computing MST for graph G=(V,E):
- start from any vertex v and empty MST
- 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
- 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
|