Prim's Algorithm | Graaf lib (original) (raw)

Prim's algorithm computes the minimum spanning tree (MST) of a connected, undirected graph with weighted edges. Starting with an arbitrary vertex, the algorithm iteratively selects the edge with the smallest weight that connects a vertex in the tree to a vertex outside the tree, adding it to the MST.

The algorithm's worst-case time complexity is O(∣E∣log∣V∣).

Unlike Kruskal's algorithm, Prim's algorithm works efficiently on dense graphs. A limitation is that it requires the graph to be connected and does not handle disconnected graphs or graphs with negative-weight cycles.

Prim's MST is often used in network design, such as electrical wiring and telecommunications.

template <typename V, typename E>
[[nodiscard]] std::optional<std::vector<edge_id_t> > prim_minimum_spanning_tree(
    const graph<V, E, graph_type::UNDIRECTED>& graph, vertex_id_t start_vertex);