Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja

kartikkukreja/Prim's MST Algorithm.py

Last active August 29, 2015 14:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kartikkukreja/9f4a476c7b5894fb08e2 to your computer and use it in GitHub Desktop.
Save kartikkukreja/9f4a476c7b5894fb08e2 to your computer and use it in GitHub Desktop.
Download ZIP
Prim's MST Algorithm
Raw
Prim's MST Algorithm.py
Let the MST contain a single vertex v, where v is any arbitrary vertex of the graph
while it is possible to add an edge (u, v) to the MST such that u ∈ MST and v ∉ MST
add v and the least-cost edge (u, v) to the MST such that u ∈ MST and v ∉ MST
return MST
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment