Implementation of Kruskal's algorithm for finding Minimum Spanning Trees in graphs for the needs of the course Advanced Topics Algorithms Implementation Technologies in Department of Computer Engineering & Informatics, University of Patras.
Header file MST.hpp contains the class MST which implements:
- Kruskal's algorithm
- A checker function
- A function that tests the worst case of the algorithm
All algorithms are implemented in C++ using structures from the LEDA library (Algorithmic Solutions Software GmbH).
In main function takes place a comparison between this algorithm and LEDA's algorithm for constructing a minimum spanning tree, for the following types of graphs:
- Random Consistent Graphs
- Grid Graphs
- Worst case scenario Graphs
Instructions:
make
./run
(Note that LEDA library is required.)