Challenge: Minimum Spanning Tree problem

Question

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

Answer 1

here is the maze generator, it barely works
https://code.sololearn.com/WQ6w071U7Mkp/?ref=app

note: the same maze looks as my code 😀

Answer 2

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.

Answer 3

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.

Answer 4

@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.

Answer 5

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

Answer 6

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.