1. MST Foundations: Prim and Kruskal's Algorithms

Getting Started with Competitive Programming

(an NPTEL course)

Module 1. MST Foundations Prim and Kruskal’s Algorithms

In this module, we introduce the Minimum Spanning Trees problem, contrast it with SSSP and discuss two popular approaches to the problem -- Prim’s Algorithm and Kruskal’s Algorithm. We implement both these problems in the context of a problem called Blingor’s Network on SPOJ and you can find this problem here.

You can refer to this chapter on Minimum Spanning Trees to find the proofs of some of the claims made in the first segment.

You can find the code shown in the second and third segments at these links:

super-embed:<div id="hyvor-talk-view"></div><script async defer type="text/javascript" src="//talk.hyvor.com/web-api/embed.js"></script>