Suppose there are a number of different houses in a town. The town decides that it wants all of the houses to be connected to each other by a road system. Not every house needs to be connected directly to each other, but you should be able to get from any house to any other house by traveling along the new roads. The town also happens to be low on funding, and can't afford to waste any extra money on building nonessential roads. Given these conditions, how do you find the road system that connects all of the houses while using the least amount of road? The answer to this is called an MST, or a Minimum Spanning Tree. You can read more about minimum spanning trees here... https://en.wikipedia.org/wiki/Minimum_spanning_tree What this project does is find the MST of a graph of points, either randomly placed or placed by you. This project finds the MST by using a method based off Kruskal's Algorithm, which is an algorithm designed specifically for finding MST's. The algorithm was written by Joseph Kruskal, and first appeared in print in 1956. https://en.wikipedia.org/wiki/Kruskal%27s_algorithm You can choose how many points you want connected (up to 100), and even position the points yourself! Be aware that the more points there are, the longer it will take to find the MST. In my opinion, anything more than 100 points takes too long to be worth waiting for, so I capped it there. 2-15 --> Instant 16-35 --> Near instant 36-50 --> 1+ seconds 51-60 --> 5+ seconds 60-75 --> 10+ seconds 75-80 --> 20+ seconds 80-90 --> 30+ seconds 90-100 --> 50+ seconds 100-500 --> Possible on Scratch, but takes way too long to be worth doing. (If you're adventurous, you can remove the limit yourself) 501-Infinity --> Theoretically possible, but this program would need to be reworked to allow it, since Scratch limits projects to 500 clones/sprites.
I was first introduced to MST's in Information Technology class in school. We were tasked with creating our own algorithms for finding MST's (using pencil and paper, for humans to follow). I was actually able to come up with an algorithm similar to Kruskal's. Here's what mine was; 1. Sort all of the possible edges between any two points from the lightest to the heaviest. 2. Go through the list, adding in the edges from lightest to heaviest until all of the points were connected to every other point. 3. Search the created tree for any cycles (points that are connected in a loop). when a cycle is found, get rid of the heaviest edge in the cycle to break it. 4. Once there aren't any more cycles, the created tree is the MST. Note that the "weight" of an edge isn't necessarily the length of it. In real life, the weight is usually how expensive it would be to make that edge, like if it's a water pipe or electrical cable or something. In this project, though, the weight of an edge is equal to it's length to keep things simple and easy to visualize. The only real difference between my algorithm and Kruskal's is that Kruskal's detects cycles before adding an edge to the tree, whilst mine looks for cycles after adding enough edges to connect all the points. I originally wanted to make this project based off my algorithm, but it's very difficult for computers to "look" for cycles in a completed tree and then erase the heaviest edge in a cycle. I decided to use Kruskal's Algorithm after the project started getting way too complicated when I tried implementing mine. This project will theoretically work with any whole number of at least 2 points, but will take a really long time to do so. That's why I capped it at 100. (And also, I don't think Scratch lets you have more than 500 sprites, either clones or not clones) It took me about 3 days to get this to work, I'd guess about 15 hours of work in total. This project isn't for school or anything, I just wanted to see if I could make it using Scratch. (I also later realized that I might be able to put this in a portfolio.) December 10th Update - In an attempt to make the program run faster, I changed the sorting algorithm from Selection Sort to Quick Sort. Quick Sort is supposedly much faster and more efficient than Selection Sort, but also more complicated. It took a lot of work, and now the program is about 4 seconds faster when doing 50 points. Not too much of an improvement... but oh well.
