Be the first user to complete this post

  • 0
Add to List
Hard

281. Prim’s Algorithm - Minimum Spanning Tree (MST)

What is Prim’s algorithm?

  1. Prim's algorithm is a greedy algorithm.
  2. It finds a minimum spanning tree for a weighted undirected graph.
  3. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
  4. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

Example:

Minimum Spanning Tree (MST) Example

How to implement Prim’s algorithm?

  1. Start with the empty spanning tree.
  2. Maintain a set mst[] to keep track to vertices included in minimum spanning tree.
  3. Assign a key value to all the vertices, (say key []) and initialize all the keys with +∞ (Infinity) except the first vertex. (We will start with this vertex, for which key will be 0).
  4. Key value in step 3 will be used in making decision that which next vertex and edge will be included in the mst[]. We will pick the vertex which is not included in mst[] and has the minimum key. So at the beginning the first vertex will be picked first.
  5. Repeat the following steps until all vertices are processed
    1. Pick the vertex u which is not in mst[] and has minimum key.
    2. Add vertex u to mst[].
    3. Loop over all the adjacent vertices of u
      • For adjacent vertex v, if v is not in mst[] and edge u-v weight is less than the key of vertex u, key[u] then update the key[u]= edge u-v weight.
    4. Return mst[].

Please see the animation below for better understanding.

Ways to Implement:

  1. Adjacency Matrix – Searching.
  2. Adjacency List – Binary Heap
  3. Adjacency List – Priority Queue with decrease key.
  4. Adjacency List - Priority Queue without decrease key – Better

Time Complexity:

The time complexity of Prim's algorithm depends on the data structures used for the graph and for ordering the edges by weight.

Data Structure of GraphOrderingTime Complexity
Adjacency MatrixSearchingO(|V|2)
Adjacency ListBinary HeapO(|E|log|V|)
Adjacency ListPriority Queue with decrease keyO(|E|2log|V|)
Adjacency ListPriority Queue without decrease key – Better ImplementationO(|E|log|V|)

Reference - Wiki