Maze generation with a hybrid of Prim's and Kruskal's algorithms
34All you need to find a minimum spanning tree is to pick an arbitrary partial spanning tree and evaluate its adjacent edge of lowest weight, adding it if wouldn't create a loop.
Prim's algorithm does this by growing a single tree and maintaining a priority queue of adjacent unexplored edges. Deciding whether to add an edge is trivial because you only have to check whether vertices are in the one tree already.
Kruskal's algorithm starts with a forest where every vertex is a separate tree. It always evaluates the global minimum, which is necessarily also the local minimum. It uses a disjoint-set data structure to check connectivity of many trees efficiently.
The hybrid algorithm starts like multiple instances of Prim's algorithm. I made them share the same priority queue, although that isn't required if you take some precautions.* These instances would ordinarily create disjoint trees because the algorithm doesn't distinguish between different trees, assuming there's a connection somewhere already when it encounters another tree. The hybrid algorithm uses the disjoint-set data structure powering Kruskal's algorithm to check connectivity, allowing those trees to merge as needed.
*As long as the trees are separate, you can evaluate them in arbitrary order. When trees merge, you must then also merge their priority queues. Edges that exist in both queues will be evaluated multiple times, so be careful.
I've now done it and added more stuff: https://www.youtube.com/watch?v=l_2_KKkoXk0
There isn't really an advantage to doing this. In fact, you get to deal with the overhead of both algorithms. It's more of an educational thing to show what makes minimum spanning trees tick in greater generality.