Implementation of Minimum Spanning Tree (MST) Using Boruvka's Algorithm
video.mov
git clone https://github.com/raghavtwenty/selbac.git
cd selbac/code/
pip install -r requirements.txt
python main.py
http://127.0.0.1:5000/
A cable service provider is tasked with efficiently connecting a network of houses with TV cable connections. Utilize Boruvka's algorithm to recommend the most optimal path for connecting these houses, ensuring minimal total cable length and efficient coverage.
Design and Analysis of Algorithms
Implement Boruvka's algorithm, Provide user friendly interface, Cables (Selbac) cost estimator.
The Boruvka (also known as Boruvka's) algorithm is a classical method in Design and Analysis of Algorithms (DAA) for finding the Minimum Spanning Tree (MST) of a connected, weighted graph. Developed by Otakar Borลฏvka in 1926, this algorithm repeatedly adds the shortest edge from each component to a different component, thereby merging them until a single connected component is formed. The algorithm is efficient for parallel computation and lays the foundation for more advanced MST algorithms like Kruskal's and Prim's.
- Start with a graph G=(V,E) where V is the set of vertices and E is the set of edges. Initially, each vertex is considered as a separate component (tree).
- For each component, select the smallest weight edge that connects the component to any other component.
- Add all the selected edges to the MST and merge the connected components. If multiple edges are the same weight, choose any to break the tie.
- Repeat steps 2 and 3 until there is only one component left, which will be the MST.
- The algorithm terminates when all vertices are part of a single component.
- Displays Network Graph
- Finds the Optimal Path
- Minimum Spanning Tree (MST)
- Networkx Grpahs
- Flask Web framework
- Students
- Researchers
-
Home Page
-
Input Page
-
Input Page
-
Input Page
-
Output Page
-
Output Page
-
Network Graph
- FARHAAN
- NAVEEN
- RAGHAVA
END OF README