Skip to content

๐Ÿ”Œ Implementation of Minimum Spanning Tree (MST) Using Boruvka's Algorithm

Notifications You must be signed in to change notification settings

raghavtwenty/selbac

Folders and files

NameName
Last commit message
Last commit date

Latest commit

ย 

History

2 Commits
ย 
ย 
ย 
ย 
ย 
ย 
ย 
ย 

Repository files navigation

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