Tag Archives: graph

Prim’s Minimum Spanning Tree

Prim’s Minimum Spanning Tree

Spanning Tree – A tree that spans all the vertices of a connected and undirected graph .

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. 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. 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.

Spanning Tree Properties

  • for graph G(V, E), it contains exact (V-1) edges
  • Remove (E-V+1) edges
  • Maximally acyclic – Means after adding an edge will be cycle
  • Minimally connected – means removable of an edge from spinning tree it will give more than one components
  • maximum possible spinning tree is V ^ (V-2)


  • It’s a greedy algorithm
  • It can be implemented in various ways -like
    • By priority queue {@link PrimMinimumSpanningTree}
    • By fibonaci heap
    • By Binary heap
    • Here we’ll implement in simple way though its not optimised
How Prim’s works:
  • Maintain two collections of vertices one that added to output and another that still not process.
  • Take distance map for each vertex any add infinity for each vertices
  • Take any random vertex and and assign distance to this is 0.
  • Now iterate till all vertices not added to MST collection.
  • And a vertices from distance map who has smallest distance and that vertex is not added in MST collection
  • Process all adjacent vertices at are not added in MST collection and distance is lesser
  • All these vertices update parent map and distance map
  • Repeat this till all vertices not added to MST collection
  1. Create distance array and assign INFINITY for vertex
  2. Create parent vertex array
  3. Create visited boolean array
  4. Take any random vertex for example v0
  5. Set distance[v0]=0
  6. Set parent [v0] = -1 or null based parent data type
  7. Now Iterate from V0 to Vn-1
    1. Take vertex u which has smaller distance in distance array and not visited yet
    2. Set visited[u] = true
    3. Iterate all adjacent vertices(v) of vertex u
      1. If visited[v] = false and distance[v] < graph[u][v] then
        1. distance[v] = graph[u][v]
        2. parent[v] = u


Latest Source Code:
Github: PrimMinimumSpanningTree.java


 Edge   Weight
0 - 1 -- 2
1 - 2 -- 3
0 - 3 -- 6
1 - 4 -- 5