[ALGO] Prim's Minimum Spanning Tree

[bobluppes]

Prim's Minimum Spanning Tree

Prim's algorithm is a greedy algorithm which finds a minimum spanning tree for a (weighted) undirected graph. See the wikipedia entry for more details.

Syntax

The algorithm should have the following syntax:

/**
 * Computes the minimum spanning tree (MST) of a graph using Prim's algorithm.
 *
 * @tparam V The vertex type of the graph.
 * @tparam E The edge type of the graph.
 * @param graph The input graph.
 * @param start_vertex The starting vertex for the MST construction.
 * @return An optional containing a vector of edges forming the MST if it exists, 
 *         or an empty optional if the MST doesn't exist (e.g., graph is not connected).
 */
template <typename V, typename E>
[[nodiscard]] std::optional<std::vector<typename graph<V, E, graph_type::UNDIRECTED>::edge_t>>
prim_minimum_spanning_tree(const graph<V, E, graph_type::UNDIRECTED>& graph, vertex_id_t start_vertex);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/minimum_spanning_tree.h.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/minimum_spanning_tree_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[unbalancedvariance]

Hey can i work on this issue?

[bobluppes]

Hey can i work on this issue?

Hi, this has been in progress for quite some 😬
All logic should already be there, so I will aim to finish up the tests this week and open the PR.

I hope the other issue regarding negative weight cycles looks interesting to you as well. If you have any proposals for new algorithms to implement, feel free to open an issue or discuss it on our discord. I will create new algorithm tickets coming week as well.