Skip to content

A tool to visualize how algorithms for finding minimum spanning trees work. Complete with random generation of tree structures using Delaunay triangulation or option to import your own.

License

Notifications You must be signed in to change notification settings

Blargian/min_span_tree_visualizer

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Minimum Spanning Tree Algorithm Visualizer 🌴

A C++ project to visualize how two of the most common minimum spanning tree (MST) algorithms work - mainly Kruskal's and Prim's. The application allows the user to randomly generate a tree structure or to import one from a file, and then select which algorithm to use to find the MST. Helpful playback functionality is implemented so that the user can visually see step by step how the algorithms arrive at the final solution. User has the ability to step through the algorithm solving process step by step, or select a playback speed and watch it work it's magic.

Recording 2023-05-13 at 19 01 42

The project was inspired by the following two youtube videos, which I thought would be fun to try implement myself in C++:

Prim's Algorithm Animation

Kruskal's Algorithm Animation

Technologies

  • C++
  • CMake
  • Dear ImGui
  • Catch2

About Minimum Spanning Trees

In computer science, a graph is a collection of nodes which are connected together by edges, which have some associated weighting. In practical terms a weight might give the edge between two nodes some physical meaning such as distance in meters, time in hours or cost in dollars. A tree is a graph without cycles. i.e) constructed in such a way that there is no path of edges that can be followed which which will allow you to arrive back at the same node you left from. A spanning tree is therefore a subgraph of some graph which "spans", or connects, all the vertices of the graph. This spanning tree can also be a 'minimum' spanning tree (MST) when it is selected in such a way as to select edges which have a minimum weight when summed. It turns out that MSTs are pretty useful in many optimization problems, and in actual fact the first MST algorithm was discovered while designing an electricity network for the city of Moravia. 1

Whilst the first algorithm to be discovered for solving this problem was invented by Czech mathematician Otakar Borůvka, the two most popular algorithms today are Prim's and Kruskal's which are examples of greedy algorithms that work in slightly different ways.

🌳 Prim's Algorithm

Prim's algorithm is a greedy-algorithm which constructs the MST one edge at a time by examining all outgoing edges from some starting node, and adding the edge with lowest weight to the MST. In this way the MST is built successively until all edges have been explored.

🌲 Kruskal's Algorithm

In the same way that Prim's algorithm builds the MST one edge at a time, Kruskal's algorithm also does so, however it does so by starting off with a number of disjoint sets of edges between nodes and successively joins the sets together by edges of least weight until there is only one remaining set of edges which is the MST.

🎄 Chazelle's Algorithm (coming soon)

Chazelle's algorithm is an almost linear time algorithm for finding an MST.

Local development guide Windows

git clone the repository to your local machine.

from the root directory of the repository run:

git clone https://github.com/Microsoft/vcpkg.git

Once done, cd to the vcpkg folder and run:

./bootstrap-vcpkg.sh

Finally, run:

./vcpkg integrate install

run cd .. cd build and then run cmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake. If all goes well you will see the "Build files have been written to..." message. You may now open the generated 'minimum_spanning_tree_visualizer' project.

To run the tests, right-click and "select as startup project":

image

To run the tests, right-click and "select as startup project":

image

Footnotes

  1. O jistém problému minimálním (On a certain minimal problem)