Add Borůvka's algorithm for minimum spanning trees
- Vorherrschende Sprache
- C++
- Sterne
- 413
- Forks
- 67
- Ø Merge
- 7 Std. 24 Min.
- Gemergte PRs (30 T.)
- 53
Beschreibung
## 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.
Beitragsleitfaden
Rechercherichtung
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/.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Bewertung
- Tech-Stack
- cpp
- Issue-Typ
- Feature
- Schwierigkeit
- 4/5
- Geschätzter Aufwand
- 3-5 Tage
- Aktivitätsstatus
- Aktiv
- Klarheit
- Klar beschrieben
- Anfängerfreundlichkeit
- 45/100