This project was undertaken as part of our Algorithms course. The primary objective of this project is to implement and analyze Kruskal's algorithm for finding the Minimum Spanning Tree (MST) in a graph. The project also explores connected components within a graph, providing a comprehensive toolkit for graph analysis.
The implementation includes detailed exploration of graph generation, MST computation, and connected components analysis, along with performance benchmarks to illustrate the efficiency of Kruskal's algorithm.
- Implement Kruskal's algorithm in Python.
- Analyze the performance of Kruskal's algorithm in various scenarios.
- Develop tools for graph generation and connected components analysis.
- Provide visualizations to demonstrate the results of the algorithm.
- Graph Theory
- Kruskal's Algorithm
- Union-Find Data Structure
- Performance Benchmarking
- Visualization of Graphs and MST
The implementation demonstrates the efficiency of Kruskal's algorithm in finding the MST of a graph. The project also highlights the importance of the Union-Find data structure in optimizing the algorithm's performance. The visualizations provide a clear understanding of the MST and the connected components within the graph.