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.

Let us define the MSTPrim class inheriting the MST interface:

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:

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);
    }
}

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));
}

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

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