+ 3

# 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

1st Sep 2017, 2:44 AM
Denis Felipe
+ 2
here is the maze generator, it barely works https://code.sololearn.com/WQ6w071U7Mkp/?ref=app note: the same maze looks as my code 😀
3rd Sep 2017, 1:13 AM
ysraelcon
+ 1
Ah, Im understanding the algorithm, here a simple one that barely works :) https://code.sololearn.com/WxPYx41245R7/?ref=app plus perhaps I'll do a maze generator with it.
1st Sep 2017, 2:25 AM
ysraelcon
+ 1
Yeah, you can create maze generators if you run the algorithm in a grid graph. In that case, the algorithm needs to make sure only existing edges are considered.
1st Sep 2017, 2:40 AM
Denis Felipe
+ 1
@ysraelcon Your algorithm seems to work, but it is not optimized. You could gain some performance if you improved the time it takes to find the closest unmarked vertex of the graph. But for small instances of the problem, your algorithm seems to be just fine.
2nd Sep 2017, 11:21 AM
Denis Felipe
0
interesting, I think I've used it on here https://code.sololearn.com/WOrT77hhCnd0/?ref=app because it is mentioned on this challenge: https://www.sololearn.com/Discuss/567313/?ref=app plus I'm researching about
31st Aug 2017, 12:47 AM
ysraelcon
0
I fail to see how you use minimum spanning tree to solve that problem. It is clearly a dynamic programming problem, so maybe you are mistaking it for a backtracking or something similar in a decision tree.
31st Aug 2017, 9:37 AM
Denis Felipe