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
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
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 ∪
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.