How Prim's Algorithm Works | wandertechmark

Definition

A spanning tree of an undirected connected graph is its connected acyclic subgraph (i.e., a tree) that contains all the vertices of the graph. If such a graph has weights assigned to its edges, a minimum spanning tree is its spanning tree of the smallest weight, where the weight of a tree is defined as the sum of the weights on all its edges.

The minimum spanning tree problem is the problem of finding a minimum spanning tree for a given weighted connected graph.

Graph and its spanning trees

In the above figure, T1 is the minimum spanning tree.

If we were to try constructing a minimum spanning tree by exhaustive search, we would face two main obstacles.

• First, the number of spanning trees grows exponentially with the graph size (at least for dense graphs).

• Second, generating all spanning trees for a given graph is not easy; in fact, it is more difficult than finding a minimum spanning tree for a weighted graph by using one of several efficient algorithms available for this problem.

So, Prim’s Algorithm constructs a minimum spanning tree through a sequence of expanding subtrees. The initial subtree in such a sequence consists of a single vertex selected arbitrarily from the set V of the graph’s vertices.

1. On each iteration, the algorithm expands the current tree in the greedy manner by simply attaching to its nearest vertex not in that tree.
2. The algorithm stops after all the graph’s vertices have been included in the tree being constructed.

Here is the Pseudocode of this Algorithm:

//Prim’s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G = {V, E} 
//Output: ET , the set of edges composing a minimum spanning tree of G
VT ← {v0} //the set of tree vertices can be initialized with any vertex
ET ← ∅
for i ← 1 to |V| − 1 do 
        find a minimum-weight edge e∗ = (v∗, u∗) among all the edges (v, u)
        such that v is in VT and u is in V − VT
        VT ← VT ∪ {u∗} 
        ET ← ET ∪ {e∗} 
return ET

The nature of Prim's algorithm makes it necessary to provide each vertex not in the current tree with the information about the shortest edge connecting vertex to a tree vertex.

Here vertices are not adjacent to any of the tree vertices can be given the ∞ label indicating their "infinite" distance to the tree vertices and a null label for the name of the nearest tree vertex.

• After we have identified a vertex u∗ to be added to the tree, we need to perform two operations:

1. Move u∗ from the set V − VT to the set of tree vertices VT.
2. For each remaining vertex u in V − VT that is connected to u∗ by a shorter edge than the u’s current distance label, update its labels by u∗ and the weight of the edge between u∗ and u, respectively.

Application of Prim's algorithm

Note: In the above image the parenthesized labels of a vertex in the middle column indicate the nearest tree vertex and edge weight; notice that selected vertices and edges are shown in bold.

You might get a question here that "Does Prim's algorithm always yield a minimum spanning tree?"  The answer to this question is yes.

Proof:

Let us prove by induction that each of the subtrees Ti, i = 0, ..., n − 1, generated by Prim’s algorithm is a part (i.e., a subgraph) of some minimum spanning tree.

• The basis of the induction is trivial, since T0 consists of a single vertex and hence must be a part of any minimum spanning tree.

• For the inductive step, let us assume that Ti−1 is part of some minimum spanning tree T.

• We need to prove that Ti, generated from Ti−1 by Prim’s algorithm, is also a part of a minimum spanning tree.

• We prove this by contradiction by assuming that no minimum spanning tree of the graph can contain Ti. Let ei = (v, u) be the minimum weight edge from a vertex in Ti−1 to a vertex not in Ti−1 used by Prim’s algorithm to expand Ti−1 to Ti.

• By our assumption, ei cannot belong to any minimum spanning tree, including T. Therefore, if we add ei to T, a cycle must be formed.

Correctness Proof of Prim's algorithm

Time Complexity of Prim's Algorithm

Deletion of the smallest element from and insertion of a new element into a min-heap of size n are O(log n) operations, and so is the operation of changing an element’s priority.

1. If a graph is represented by its adjacency lists and the priority queue is implemented as a min-heap, the running time of the algorithm is in O(|E| log |V|).

2. This is because the algorithm performs |V| − 1 deletions of the smallest element and makes |E| verifications and, possibly, changes of an element’s priority in a min-heap of size not exceeding |V|.

3. Each of these operations, as noted earlier, is a O(log |V|) operation. Hence, the running time of this implementation of Prim’s algorithm is in,

(|V| − 1 + |E|)O(log |V|) = O(|E| log |V|)

Since in a connected graph,  |V| − 1 ≤ |E|.

FAQs

1. What is the Prim's algorithm?

• Prim's algorithm  is a greedy algorithm, which finds a minimum spanning tree for a weighted undirected graph.

2. What are Prims and Kruskal's algorithms?

• The Prim's algorithm starts by choosing the root vertex and moves closely from vertex to vertex.
• In contrast, starting from the smallest weighted edge, Kruskal's algorithm aids in the creation of the minimum spanning tree.

3. What is the complexity of Prims?

• The time complexity is O(VlogV + ElogV) = O(ElogV), making it the same as Kruskal's algorithm. However, Prim's algorithm can be improved using Fibonacci Heaps to O(E + logV). Time complexity is explained above👆 with equations.

4. Why Prim's algorithm is called greedy?

• Prim's algorithm enables the determination of a graph's minimum spanning tree. Because it is a greedy algorithm, it chooses the option that is currently available.

5. What is the difference between Dijkstra and Prims?

• When you specify node i, Dijsktra's algorithm determines the shortest path between it and every other node. As a result, you receive the tree with the shortest distance from node i.
• For a given graph, the Prims algorithm yields the minimum spanning tree. a tree with all nodes connected and the lowest possible total cost.