Prim's algorithm

You've already become familiar with the minimum spanning tree (MST) – the concept that is widely used in many fields, including machine learning, cluster analysis, network design, and urban planning. However, to use it successfully, you need to know the algorithms, that help to find the MST. This topic is exactly about one of them – Prim's algorithm. So, let's learn about it right now!

The algorithm

Before diving into the algorithm, let's remember some important definitions. Firstly, a spanning tree is such a subgraph of the initial graph, that is a tree and connects all of its vertices. Consequently, a minimum spanning tree is a spanning tree with the minimum possible sum of the weights of its edges.

Now, it is time to move on to the algorithm itself. Prim's algorithm allows us to find a minimum spanning tree in an undirected connected weighted graph. The algorithm starts constructing a tree with a single node. At each step, it considers all edges $\{x, y\}$ such that $x$ is a node of the current tree and $y$ is not. Among all such edges, you add the one with the smallest weight to the current tree. So, the algorithm is greedy: at each step, an edge giving the best possible advantage is selected. The steps of the algorithm are the following:

1. Select any node in a graph as the first node of a spanning tree.

2. Consider all edges $\{x, y\}$ such that $x$ is a node of the current tree and $y$ is not.

3. Among all such edges, choose the one with the smallest weight and add it to the current tree.

4. Repeat steps 2-3 while there are edges that can be added to the current tree. Then, return the resulting tree as a final answer.

Can we be sure that this algorithm doesn't form cycles in a resulting graph? Actually, we can! Indeed, after each iteration of the algorithm, we add a new vertex to the tree. If at some point a cycle appeared, it would mean that this node is already connected to some vertex of the tree. But it is a contradiction since we add only those vertices, that have not been added to the tree yet.

Phew, that's it! Now, it is a great idea to apply this theory to an actual graph, so don't wait and move on to the section with the example right away!

An example

Let's consider how the algorithm works for the following graph:

In the figures below, the nodes and the edges of the current tree are shown in blue, and the edges that are candidates to be added to the current tree will be shown in green.

We start constructing a minimum spanning tree with the node $0$. There are three edges that are incident to this node: $\{0, 1\}, \{0, 2\}$ and $\{0, 3\}$. The edges $\{0, 1\}$ and $\{0, 2\}$ have the smallest weight. Let's choose the first edge and add it to the current tree. At the next step, the edge $\{0, 2\}$ is the one, that is added to the tree, as it has the smallest weight.

Then, we can choose either $\{0, 3\}$ or $\{1, 3\}$. We choose the first edge and add it to the tree. After that, the edge $\{3, 5\}$ is added to the tree. These steps are shown in the picture above (steps 3 and 4).

Continuing the same process we finally get a spanning tree shown in Figure 8. The resulting minimum spanning tree consists of $7$ edges and has a weight of $1 + 1 + 2 + 3 + 2 + 1 + 2 = 12$.

Complexity analysis

Since the essence of the algorithm should be clear by now, it is time to discuss its complexity. Suppose that a graph $G$ has $V$ nodes and $E$ edges. The running time of Prim's algorithm depends on the representation of the graph and the data structure used for finding an edge with the smallest weight.

1. Using an adjacency matrix with no additional data structures: we may use an adjacency matrix to store the graph. This algorithm proceeds in $V-1$ steps since a minimum spanning tree (MST) of a graph with $V$ nodes has $V-1$ edges. In each step, the algorithm selects the edge with the smallest weight among all the edges that connect a node inside the MST to a node outside the MST. The crucial part that affects the running time is the step where we find the edge with the smallest weight. Considering that the size of the adjacency matrix is $V \times V$ ($V^2$ elements), and there are $V-1$ steps, the overall running time would be $O(V^3)$ for this approach. This is because in each of the $V-1$ steps, we check all $V^2$ elements of the matrix, resulting in a time complexity of $O(V^2)$ per step. Hence, the total running time is $O((V^2) * (V−1)) = O(V^3)$.

2. Using an adjacency matrix and an additional list/array: in this approach, we use a list or an array of length $V$ to store the edge of minimum weight, connecting each vertex to the MST. At each step, we find the edge with the smallest weight from this list or array and add it to the MST. However, finding the smallest weight edge in the list/array would require $O(V)$ operations. Another important operation is updating neighbors in $O(V)$ time: after adding a new edge $\{x, y\}$ to the MST, we may need to update the minimum-weight edges of the neighboring nodes of $y$, that have not been connected to the MST yet. This updating process can be done in $O(V)$ time by considering all the neighbors of $y$. Overall running time for this approach: since Prim's algorithm has $V-1$ steps ($V$ nodes in the MST), the overall running time would be $O(V^2)$ due to the $O(V)$ operations for finding the smallest weight edge and the $O(V)$ operations for updating the neighbors.

3. Using an adjacency list and an additional binary heap: to decrease the running time, we can use a binary heap to store current edges with the smallest weight for each vertex. Remember that a binary heap is a data structure that always allows us to retrieve the element with the smallest (or largest) value efficiently. When adding edges to the binary heap, we ensure that the edge with the smallest weight is always at the top, making it easy to retrieve. Updating and finding an edge in a binary heap takes $O(log\ V)$ time. This is more efficient than the $O(V)$ time taken in the approach using a list or an array. Overall running time for this approach: the overall running time is $O(E\ log\ V + V\ log\ V) = O(E\ log\ V)$, where $E$ is the number of edges in the graph and $V$ is the number of nodes. You may wonder: why is it like this? Well, the $O(E\ log\ V)$ part comes from the time taken to insert all the edges into the priority queue. The $O(V\ log\ V)$ part arises from the operations of extracting the edge with the smallest weight from the priority queue. Since there are $V$ nodes, for each of which an edge is extracted strictly once, the total number of operations is $O(V\ log\ V)$.

Right now it may seem that the third approach is superior in terms of complexity, so it should be used instead of the other ones mentioned. However, the strategy may change, depending on the type of the graph:

• For sparse graphs $(E \approx V)$, where the number of edges is approximately equal to the number of nodes, the overall running time of the third approach is $O(V\ log\ V)$, which is why it is more efficient than the other ones.

• For dense graphs $(E \approx V^2)$, where the number of edges is close to the maximum possible ($V^2$ edges in a V-node graph), the overall running time becomes $O(V^2\ log\ V)$. In this case, the approach using a binary heap is slower than the approach described in step 2 ($O(V^2)$), making the latter more efficient for dense graphs.

Pseudocode

What may be more important than understanding the algorithm? Being able to implement it, of course! Therefore, let's look at the pseudocode for the approach, that uses the binary heap. In order not to overcomplicate it the implementation of the binary heap is missing, but you can learn about it from the prerequisites.

class Prim:  
  function find_tree(graph):  
    tree_edges = [] 
    min_heap = Heap() 
    
    // initializing minimum weigths for each edge with a maximum possible value 
    min_edges = [Int.maxValue()] * length(graph) 
    
    // we are going to start our tree with the node 1, so the weight for it is the least among the vertices 
    // this way it will be extracted first 
    min_edges[1] = -1 
    // for storing the starting node of the edge with minimum weight 
    min_edge_parents = [-1] * length(graph) 

    // inserting our edges into a heap 
    for i in [1, length(graph)]: 
      insert(min_heap, [i, min_edges[i]]) 

    while size(min_heap) > 0: 
      // extracting the node, which is connected to a tree by an edge of the minimum weight 
      cur_node = extract_min(min_heap) 
      // adding an edge to our current tree 
      tree_edges.add(Edge(cur_node, min_edges_parents[cur_node], min_edges[cur_node]))
      
      // going through all of the edges to the incident nodes 
      for edge in graph[cur_node]: 
        child = edge.destination
        
        // if a node is still not connected to the tree and the edge's weight is smaller then 
        // the one of the current candidate, update the values 
        if (contains(min_heap, child) and min_edges[child] > edge.weight) then 
          min_edges[child] = edge.weight 
          min_edge_parents[child] = cur_node 
          insert(min_heap, [child, edge.weight]) 

    return tree_edges 

Conclusion

To sum up, let's go through the main aspects of the Prim's algorithm:

1. It is a greedy algorithm.

2. It is used to find the minimum spanning tree (MST) of the graph.

3. The algorithm starts constructing a tree with a single node. At each step, it considers all edges $\{x, y\}$ such that $x$ is a node of the current tree and $y$ is not. Among all such edges, the one with the smallest weight is added to the current tree.

4. The time complexity of the algorithm changes, depending on the data structures used: for an adjacency matrix it is $O(V^3)$, for the list or array it is $O(V^2)$ and with the use of a binary heap it may be reduced to $O(E\ log\ V + V\ log\ V) = O(E\ log\ V)$.

5. For sparse graphs, it is more efficient to use the approach with the binary heap, and for dense ones – with the use of list/array.