Tag Archives: graph

Prim’s Minimum Spanning Tree

Leave a reply

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)

Solution:

  • 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
Algorithm:
  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

Video

Latest Source Code:
Github: PrimMinimumSpanningTree.java


Output:

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