Graph Theory: Minimum Spanning Trees
Graph theory is a branch of math dealing with graphs, which are dots and lines. You represent structures with a graph, and then you can apply graph theory to gain insights. A group of friends is a graph. Perhaps one friend knows everyone, while another friend only knows a few people in the group. The popular friend is a dot with many lines to other dots, whereas the unpopular friend is a lone dot with only a few lines to other dots. You see how this works.
A tree appears if we remove all the cycles from the graph and ensure that every friend is connected to at least one other friend. Therefore, the popular friend’s friends cannot be talking to one another; otherwise, there would be a triangle in the graph, which would mean I can travel in a cycle along the graph between these three people.
A Minimum Spanning Tree is a tree where the cost from going from one node to any other is minimized. Suppose we examine a University’s internal internet network. From each building, there are connections to the other buildings. Some connections are distant and high latency; other connections are fast. If we modelled this as a graph, with the fast connections being low-cost and the slow connections being high-cost, a Minimum Spanning Tree would show us the fastest connection from our building to any other building.
This app you see applies Prim’s algorithm for computing a minimum spanning tree for an arbitrary graph.
My first app, written in Java
This is the first app I ever coded up. I did it in Java use a clunky old Java IDE, and it was an excellent but difficult coding experience. The code is up on Github for your perusal if you wish to see it: https://github.com/louisritchie/Prims_Algorithm.
