bobluppes / bobluppes/graaf

Add Borůvka's algorithm for minimum spanning trees

Open
#335 0 comments 0 reactions 0 assignees View on GitHub
enhancement good first issue help wanted
Dominant language
C++
Stars
413
Forks
67
Avg merge
7h 24m
Merged PRs (30d)
53

Description

## Summary

Graaf implements two minimum-spanning-tree algorithms (Kruskal, Prim) but not a third standard one: Borůvka's algorithm.

## Current state

`include/graaflib/algorithm/minimum_spanning_tree/` contains only `kruskal.h`/`.tpp` and `prim.h`/`.tpp`. There is a related historical request, [#113 "[ALGO] Borůvka's algorithm"](../issues/113), which was closed without being implemented (closed due to inactivity, not as "won't do").

## Why this matters

Borůvka's algorithm is one of the three classical MST algorithms taught and used alongside Kruskal's and Prim's, and it has a property neither of the other two has out of the box: it parallelizes naturally, since each iteration finds the minimum outgoing edge for every component simultaneously. For a library whose own MST category already covers two of the three standard approaches, omitting the third — particularly the one most relevant to parallel/large-scale processing — is a visible completeness gap for anyone comparing MST algorithm coverage against alternatives like Boost Graph Library.

## Suggested resolution

- Implement Borůvka's algorithm under `include/graaflib/algorithm/minimum_spanning_tree/`, following the existing `kruskal`/`prim` structure.
- It can reuse the union-find data structure if that's extracted into a public, reusable class (see the related union-find issue) rather than duplicating Kruskal's private helper.
- Add corresponding documentation under `docs/docs/algorithms/minimum-spanning-tree/`, including complexity and how it compares to Kruskal's and Prim's.

## Acceptance criteria

- [ ] Borůvka's algorithm is implemented for undirected weighted graphs.
- [ ] Documentation added, including complexity and a comparison with the existing Kruskal/Prim implementations.
- [ ] Unit tests cover connected graphs, disconnected graphs (minimum spanning forest), and graphs with equal-weight edges.

Contributor guide

Open the contributing guide

Research direction

The algorithm should be added to include/graaflib/algorithm/minimum_spanning_tree/. Study the existing kruskal.h/.tpp and prim.h/.tpp to understand the interface and structure. The union-find data structure may need to be reused or extracted. Write unit tests for connected graphs, disconnected graphs, and equal-weight edges. Documentation should be added under docs/docs/algorithms/minimum-spanning-tree/.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.