In Graph Theory, a graph is defined as a collection of vertices and edges, where vertices correspond to entities and an edge between two vertices implies that the corresponding entities are somehow related. Edges can have weights reflecting a kind of cost required for their establishment, such as distance, time or budget. Trees are special cases of graphs which are acyclic and connected. A Spanning Tree for a given graph is a tree containing all vertices of this graph. When weights are assigned to the edges of a graph, a Minimum Spanning Tree (MST) for this graph is a spanning tree of minimum total edge-cost. Given a connected graph, we can efficiently (i.e., fast) compute a Minimum Spanning Tree for this graph using two well-known algorithms from the literature, one suggested initially by Vojtěch Jarník and later by Robert Prim and one suggested by Joseph Kruskal, which return similar results though in a slightly different fashion. The MST problem has various practical applications in real-world instances where we seek for minimum-cost solutions for connecting all involved points of interest.

In this work, we present a web application for the computation of Minimum Spanning Trees (MST) for user-defined graphs which can be either random or manually drawn on a canvas. Our main intention with this application is to provide an additional tool for students to support their study mainly within courses on Introduction to Algorithms but also in the context of courses utilizing the MST construct. Of course, our MST calculator can be exploited by all interested users when their activities involve MST computations.

Our application contains the main section and a training section. In the main section, users can set-up an instance of the MST problem by first providing the initial graph and then selecting the desired method, i.e., Kruskal’s or Prim’s algorithm, for the MST computation. The initial graph can be either a user-defined random graph or it can be manually drawn on a canvas. Users can select between just receiving the computed MST and observing the whole computational procedure in a step-by-step fashion. Users can download computed MSTs as .png files. In the training section, users can practice on the application of Kruskal’s and Prim’s algorithms for the MST problem. In particular, users are presented with a graph automatically generated by the application and the method they are expected to apply. Then users must gradually build an MST by selecting edges until all vertices of the given graph are connected. The computed MST is evaluated by the application and in case of incorrect answers corrections are indicated directly on the user-computed MST.

Compared to other existing relevant applications, the innovative nature of our application mainly stems from its educational focus. More precisely, unlike existing approaches, our application allows users to familiarize with random graphs, a model capturing real-world scenaria, and also enables them to directly draw their desired initial graph. Also, our application enables users to exploit both algorithms in a single interface and run them also in a step-by-step fashion thus letting them experimentally and even visually compare how these algorithms build MSTs. Our application is responsive, currently offered in greek and english and has been developed using React.

Keywords: Educational web app, responsive, Minimum Spanning Tree (MST) problem, Kruskal's algorithm, Prim's algorithm, random graphs, React.