Notes

Earlier last quarter, I remember one of my friends really liked to doodle in the form of randomly drawing mazes. He decided to draw one for me, and I joked that I was going to scan it into a computer and tell the computer to solve it for me.
But that did get me thinking about maze solving algorithms. It did seem a bit interesting, but when I was scrolling through wikipedia articles, something else caught my eye. It was actually an article on algorithms that generates mazes in the first place. I had never really thought about the fact that people needed algorithms to randomly generate these mazes, but I suppose it does make sense. Although, it does make me a bit sad that the mazes I did on the back of cereal boxes in my elementary school days were probably not hand-crafted with care

Still though, I did find this idea really cool, and I quickly found myself mesmerized by some of the really cool "oddly satisfying" animations on the page. From a purely mathematical perspective, I was also reminded of many of the concepts taught in my discrete structures course last year, and how these were some pretty direct but cool applications of those concepts.
In particular, the one that I became most interested in was the adaptation of Prim's algorithm for this maze generation. For those of you who don't know, Prim's algorithm has to do with graphs, and more specifically, what are called "minimal spanning trees" within a graph.
First off, what's a spanning tree? Let's say you're given a graph with weighted edges, and you want to trim off as much of the excess fat as possible, i.e. remove as many edges as possible without removing any