Okay, imagine that there are a bunch of houses and you make sidewalks. You want to connect the houses with direct house-to-house sidewalks so that all of the houses are connected, using the smallest amount of sidewalk. That's the idea behind the Minimum Spanning Tree! The MST is a graph that is a tree (no loops, every pair of nodes (houses) is connected with just one path). In this project, N nodes are placed randomly, and the Minimum Spanning Tree is found. There are many algorithms to find the Minimum Spanning Tree. The one used here is called Prim's algorithm, and it has a mathematical guarantee that out of all the spanning trees that contain the nodes of a graph, it has the minimum possible sum of edge weights. The basic idea is to start a tree with just one edge -- the shortest edge in the graph. Then, all possible edges are examined. At each step, the *smallest* edge is added that connects to the tree to one of the nodes that are not yet connected. This repeats until the tree has N-1 edges. There are 2 modes in this project. You can drag around the points to see how the MST changes. The white edges are all those edges NOT in the MST. Using the left and right arrows, you can see the step-by-step way that Prim's method works. First, the smallest edge is added (green). At each step, one edge is added to the tree from among all of the thin yellow edges that are singly-connected to the tree. The black edges are removed -- if added they would make a loop. The white edges are those that don't touch any nodes in the Tree. Summary of the controls: "z" shows the ID of each node "a" hides the node ID "h" hides or shows the total_mst_distance "left" and "right" allow you to step through Prim's algorithm.
Summary of the controls: "z" shows the ID of each node "a" hides the node ID "h" hides or shows the total_mst_distance (useful if blocking a node). "left" and "right" allow you to step through Prim's algorithm. Check out: https://www.youtube.com/watch?v=YyLaRffCdk4 and https://en.wikipedia.org/wiki/Prim%27s_algorithm for more about Prim's algorithm.
