Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja

kartikkukreja/Kruskal'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/7eed924e5fd63438a8b7 to your computer and use it in GitHub Desktop.
Save kartikkukreja/7eed924e5fd63438a8b7 to your computer and use it in GitHub Desktop.
Download ZIP
Kruskal's MST Algorithm
Raw
Kruskal's MST Algorithm.py
sort edges in order of increasing cost
MST = {}
foreach edge (u, v) in order of increasing cost
if MST ∪ (u, v) does not create a cycle
add (u, v) to MST
return MST
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment