# Challenge: Minimum Spanning Tree problem

The minimum spanning tree problem consists in finding the set of edges that connect an undirect graph using the minimum total edge weight, resulting in a single path between any two vertices of the graph. This problem has several real life applications, like the design of optimal networks, including computer, communication, transportation, water supply and electrical grids. There are several well known algorithms to solve this problem, the most well known being Prim's and Kruskal's. The challenge is very simple: implement as many of those algorithms as possible. You will be awarded one point for each exact algorithm that solve the minimum spanning tree problem. Any language is allowed, but I will make available some auxiliary code in C++, including disjoint sets (used for kruskal), binary heap (used for prim) and a sample of prim's algorithm (avoid checking it before you try it yourself). The result should be validated in a random graph (a NxN matrix) with random weights in the range [10.0, 100.0]. The solution must include the edges of the minimum spanning tree and the total weight of those edges. The challenge will take two weeks, but can be extended depending on the number of people. For obvious reasons, any pre-defined functions that solve the problem on their own are not allowed. Have fun! Binary Heap: https://code.sololearn.com/cLHG0A9EGu49/#cpp Disjoint Sets: https://code.sololearn.com/cwsgAQnRpYyD/#cpp Random Number Generator: https://code.sololearn.com/c9JJ5j9VxdD2/#cpp Instance generator and Prim's algorithm: https://code.sololearn.com/cpcbN88XIjhk/#cpp Example in a real life problem: https://code.sololearn.com/cPcX1jgm1o2Y/#cpp