Kruskal’s Algorithm

Learn about Kruskal’s algorithm and its applications in solving the minimum spanning trees problem.

Introduction to Kruskal’s algorithm

The last minimum spanning tree algorithm we’ll consider was first described by Joseph Kruskal in 1956, in the same paper where he rediscovered Jarník’s algorithm. Kruskal was motivated by “a typewritten translation (of obscure origin)” of Borůvka’s original paper that had been “floating around” the Princeton Math department. Kruskal found Borůvka’s algorithm “unnecessarily elaborate.” The same algorithm was rediscovered in 1957 by Harry Loberman and Arnold Weinberger but somehow avoided being renamed after them.

Methodology

Like our earlier minimum spanning tree algorithms, Kruskal’s algorithm has a memorable one-line description:

  • Kruskal: Scan all edges by increasing weight; if an edge is safe, add it to FF.

In the below illustration, Kruskal’s algorithm runs on the example graph. Thick red edges are in FF; thin dashed edges are useless.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy