/**
 * @file prim_algorithm.hpp
 *
 * CopyRight F. J. Madrid-Cuevas <fjmadrid@uco.es>
 *
 * Sólo se permite el uso de este código en la docencia de las asignaturas sobre
 * Estructuras de Datos de la Universidad de Córdoba.
 *
 * Está prohibido su uso para cualquier otro objetivo.
 */
#pragma once

#include <vector>

#include "graph.hpp"

/**
 * @brief The Prim's algorithm.
 * Compute the minimum spanning tree on an undirected weighted graph using Prim's algorithm.
 *
 * @param[in] g is the graph.
 * @param[in] start_vertex is the vertex's label from which the algorithm starts (the root of the mst).
 * @param[out] mst is the list of edges of g that forms the minium spanning tree.
 * @return the total weight of the minimum spanning tree.
 * @pre !g.is_directed()
 * @post mst.size() == g.order() - 1
 * @throw std::runtime_error("It is an unconnected graph.") if the input graph
 *        is an unconnected one.
 */
template <class T>
float prim_algorithm(WGraph<T> &g,
                     size_t start_vertex,
                     std::vector<EdgeIterator<T>> &mst) noexcept(false);

#include "prim_algorithm_imp.hpp"