# 8.2. Prim's Algorithm

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?


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://emory.gitbook.io/dsa-java/minimum-spanning-trees/prims-algorithm.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.