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.
The project was inspired by the following two youtube videos, which I thought would be fun to try implement myself in C++:
- C++
- CMake
- Dear ImGui
- Catch2
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 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.
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 is an almost linear time algorithm for finding an MST.
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":
To run the tests, right-click and "select as startup project":
