Prims Algorithm

Prims algorithm

It is widely used algorithm for locating minimum Spanning Tree,Prim’s Algorithm uses Cut in Graph theory to select up the smallest amount weighted edge at each stage. Minimum Spanning Tree Spanning tree : A connected subgraph ‘S’ of graph G(V,E) is claimed to be spanning if- 1. ’S’ should contain all vertices of ‘G’ 2. ‘S’ should contain (|V|-1) edges.

Minimum Spanning Tree: If the no of vertices in graph G(V,E) is V then the no of edges is|V-1| and it should be a connected graph and therefore the cost of the burden should be minimum.

Minimum Spanning Tree: If the no of vertices in graph G(V,E) is V then the no of edges is|V-1| and it should be a connected graph and the cost of the weight should be minimum.

Minimum Spanning tree Applications

• To find paths within the map

• To design networks like telecommunication networks, water system networks, and electrical grids

Working

Prim’s algorithm works falls under a category of algorithms called greedy algorithms that find the local optimum within the hopes of finding a worldwide optimum. We start from one vertex and keep adding edges with rock bottom weight until we reach our goal.

The steps for implementing Prim’s algorithm are as follows:

1. Initialize the minimum spanning tree with a vertex chosen randomly.

2. Find all the perimeters that connect the tree to new vertices, find the minimum and add it to the tree

3. Keep repeating step 2 until we get a minimum spanning tree Pseudocode of Prims Algorithm

PSEUDOCODE

The pseudocode for prim’s algorithm shows how we create two sets of vertices U and V-U. U contains the list of vertices that are visited and V-U the list of vertices that haven’t. One by one, we move vertices from set V-U to line U by connecting the smallest amount weight edge. Steps

• Step 1: Make two U and V sets.
• •Step 2: Enter the starting value in U, from which the spanning tree are constructed.
• • Step 3: While U and V don’t seem to be equal, locate the most affordable thanks to get to the sting and place it over U.
• • Step 4: Repeat steps 3 and 4 for the remaining edges until you have got an MST T = ∅; U = ; while (U ≠ V) let (u, v) be all-time low cost edge specified u ∈ U and v ∈ V — U; T = T ∪ U = U ∪

TIME COMPLEXITY

The Worst case time complexity of Prim’s Algorithm is-

• O(ElogV) using binary heap

• O(E + VlogV) using Fibonacci heap Time Complexity Analysis • If adjacency list is employed to represent the graph, then using breadth first search, all the vertices is traversed in O(V + E) time. • We traverse all the vertices of graph using breadth first search and use a min heap for storing the vertices not yet included within the MST. • To get the minimum weight edge, we use min heap as a priority queue. • Min heap operations like extracting minimum element and decreasing key value takes O(logV) time. So, overall time complexity = O(E + V) x O(logV) = O((E + V)logV) = O(ElogV) This time complexity will be improved and reduced to O(E + VlogV) using Fibonacci heap.