An implementation of Boruvka's algorithm to find a minimum spanning tree in a graph.
Link to narrated video demonstration on YouTube.
![image](https://private-user-images.githubusercontent.com/47993930/302074394-70c6d09e-7273-4416-8194-f4fe37701ef2.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjQ1ODMwMzAsIm5iZiI6MTcyNDU4MjczMCwicGF0aCI6Ii80Nzk5MzkzMC8zMDIwNzQzOTQtNzBjNmQwOWUtNzI3My00NDE2LTgxOTQtZjRmZTM3NzAxZWYyLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA4MjUlMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwODI1VDEwNDUzMFomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPWUzN2MwNmRkY2ZmMmRjMzQyOGQ0Y2E4MmVhZGVkM2IwMGFlMjc3NjRkODhhNzA2OTU5NDNkOGY2NGVkMDgyMDQmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.ulCXznpFalS-hQ4WFyRbxxYYbwXLD2jR6FBawq92sO8)
stdout (Terminal Output)
Finding MST with Boruvka's algorithm:
Vertices: [0, 1, 2, 3, 4, 5, 6, 7, 8]
Edges (vertex_1, vertex_2, weight):
(0, 1, 4)
(0, 6, 7)
(1, 2, 9)
(1, 6, 11)
(1, 7, 20)
(2, 3, 6)
(2, 4, 2)
(3, 4, 10)
(3, 5, 5)
(4, 5, 15)
(4, 7, 1)
(4, 8, 5)
(5, 8, 12)
(6, 7, 1)
(7, 8, 3)
Iteration 1:
Current MST edges: []
Current MST Weight: 0
Added edge 0 - 1 with weight 4 to MST.
Added edge 2 - 4 with weight 2 to MST.
Added edge 3 - 5 with weight 5 to MST.
Added edge 4 - 7 with weight 1 to MST.
Added edge 6 - 7 with weight 1 to MST.
Added edge 7 - 8 with weight 3 to MST.
Iteration 2:
Current MST edges: [(0, 1, 4), (2, 4, 2), (3, 5, 5), (4, 7, 1), (6, 7, 1), (7, 8, 3)]
Current MST Weight: 16
Added edge 0 - 6 with weight 7 to MST.
Added edge 2 - 3 with weight 6 to MST.
MST found with Boruvka's algorithm.
MST edges (vertex_1, vertex_2, weight):
(0, 1, 4)
(0, 6, 7)
(2, 3, 6)
(2, 4, 2)
(3, 5, 5)
(4, 7, 1)
(6, 7, 1)
(7, 8, 3)
MST weight: 29
Run the following command from the project root directory:
poetry install
Run the following command from the project root directory:
poetry run app
Run the following command from the project root directory:
poetry run pytest