Kruskal's Algorithm

  • Initially mark all edges gray.

  • Consider edges in increasing order of weight.

  • Add edge to MST (mark black) unless doing so creates a cycle.

  • Repeat until V-1 edges.

  • Conceptual Kruskal’s Algorithm Demo (Link)

  • Realistic Kruskal’s Algorithm Implementation Demo (Link)

1. Sort all the edges from lightest to heaviest.
2. Taking one edge at a time (in sorted order), add it to our MST under construction if doing so does not introduce a cycle.
3. Repeat until there are {% math %}V-1{% endmath %} edges.

vs Prim's Algorithm