> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/minimum-spanning-trees/prims-algorithm.md).

# 8.2. Prim's Algorithm

This section discusses Prim's Algorithm that finds a minimum spanning tree in an undirected graph.

Prim's algorithm finds a minimum spanning tree by finding the minimum edge among all incoming edges of visited vertices.

{% embed url="<https://www.slideshare.net/jchoi7s/prims-algorithm-238997336>" %}

Let us define the [`MSTPrim`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/span/MSTPrim.java) class inheriting the `MST` interface:

```java
public class MSTPrim implements MST {
    @Override
    public SpanningTree getMinimumSpanningTree(Graph graph) {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        SpanningTree tree = new SpanningTree();
        Set<Integer> visited = new HashSet<>();
        Edge edge;

        add(queue, visited, graph, 0);

        while (!queue.isEmpty()) {
            edge = queue.poll();

            if (!visited.contains(edge.getSource())) {
                tree.addEdge(edge);
                if (tree.size() + 1 == graph.size()) break;
                add(queue, visited, graph, edge.getSource());
            }
        }

        return tree;
    }
}
```

* `L9`: adds the vertex `0` to the visited set and its incoming edges to the queue.
* `L11`: iterates through all incoming edges:
  * `L14`: if the visited set contains the source vertex, adding the edge would create a cycle.
  * `L16`: if the tree contains `v-1` number of edges, a spanning tree is found.
  * `L17`: repeats the process by adding the source of the edge.

The `add()` method can be defined as follows:

{% tabs %}
{% tab title="For-loop" %}

```java
private void add(PriorityQueue<Edge> queue, Set<Integer> visited, Graph graph, int target) {
    visited.add(target);

    for (Edge edge : graph.getIncomingEdges(target)) {
        if (!visited.contains(edge.getSource()))
            queue.add(edge);
    }
}
```

{% endtab %}

{% tab title="Lambda" %}

```java
private void add(PriorityQueue<Edge> queue, Set<Integer> visited, Graph graph, int target) {
    visited.add(target);
    
    graph.getIncomingEdges(target).stream().
        filter(edge -> !visited.contains(edge.getSource())).
        collect(Collectors.toCollection(() -> queue));
}
```

{% endtab %}
{% endtabs %}

* `L4-7`: adds all incoming edges that have not been visited to the queue.

> What is the worst-case complexity of Prim's Algorithm?