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
|