Skip to content

Latest commit

 

History

History
137 lines (83 loc) · 3.3 KB

README.md

File metadata and controls

137 lines (83 loc) · 3.3 KB
Raw

SELBAC

Implementation of Minimum Spanning Tree (MST) Using Boruvka's Algorithm


PROTOTYPE VIDEO

video.mov



HOW TO EXECUTE

Terminal

git clone https://github.com/raghavtwenty/selbac.git


cd selbac/code/


pip install -r requirements.txt


python main.py

Web Browser

http://127.0.0.1:5000/

PROBLEM STATEMENT

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.


DOMAIN

Design and Analysis of Algorithms


OBJECTIVE

Implement Boruvka's algorithm, Provide user friendly interface, Cables (Selbac) cost estimator.


INTRODUCTION

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.


WORKING

  1. 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).
  2. For each component, select the smallest weight edge that connects the component to any other component.
  3. 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.
  4. Repeat steps 2 and 3 until there is only one component left, which will be the MST.
  5. The algorithm terminates when all vertices are part of a single component.

FEATURES

  • Displays Network Graph
  • Finds the Optimal Path
  • Minimum Spanning Tree (MST)


TECHNOLOGIES USED

  • Networkx Grpahs
  • Flask Web framework


END USERS

  1. Students
  2. Researchers


OUTPUTS

  • Home Page

    1

  • Input Page

    2

  • Input Page

    3

  • Input Page

    4

  • Output Page

    5

  • Output Page

    6

  • Network Graph

    7


DESIGNED & DEVELOPED BY

  • FARHAAN
  • NAVEEN
  • RAGHAVA

END OF README