In computer science, Prim’s algorithm (also known as Jarník’s algorithm) is a greedy algorithm Greedy algorithm] that finds a minimum spanning tree [Minimum spanning tree] for a weighted undirected graph [Graph]. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

## Algorithm

The algorithm may informally be described as performing the following steps:

- Initialize a tree with a single vertex, chosen arbitrarily from the graph.
- Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
- Repeat step 2 (until all vertices are in the tree).

## Time complexity

- With Binary heap and an Adjacency list: \(\bigo{|E|\log(|V|)}\)
- With Fibonacci heap and an Adjacency list: \(\bigo{|E| + |V|\log(|V|)}\)

## Bibliography

## References

“Prim’s Algorithm.” 2022.

*Wikipedia*, December. https://en.wikipedia.org/w/index.php?title=Prim%27s_algorithm&oldid=1127278141.