Dynamic Programming. Explore Python Examples. Popular Examples Add two numbers. Check prime number. Find the factorial of a number. Print the Fibonacci sequence. Check leap year. DSA Introduction What is an algorithm? Prim's Algorithm In this tutorial, you will learn how Prim's Algorithm works.
Prim's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which form a tree that includes every vertex has the minimum sum of weights among all the trees that can be formed from the graph How Prim's algorithm works It falls under a class of algorithms called greedy algorithms that find the local optimum in the hopes of finding a global optimum. We start from one vertex and keep adding edges with the lowest weight until we reach our goal.
The steps for implementing Prim's algorithm are as follows: Initialize the minimum spanning tree with a vertex chosen at random.
In this case, CD is the new edge, which is less than other edges' cost 8, 6, 4, etc. After adding node D to the spanning tree, we now have two edges going out of it having the same cost, i. DT and DB. Thus, we can add either one. But the next step will again yield edge 2 as the least cost. Hence, we are showing a spanning tree with both edges included. We may find that the output spanning tree of the same graph using two different algorithms is same.
Prim's Spanning Tree Algorithm Advertisements. Previous Page. The key values are used only for vertices which are not yet included in MST, the key value for these vertices indicate the minimum weight edges connecting them to the set of vertices included in MST. Let us understand with the following example:. Now pick the vertex with the minimum key value.
The vertex 0 is picked, include it in mstSet. After including to mstSet , update key values of adjacent vertices. Adjacent vertices of 0 are 1 and 7. The key values of 1 and 7 are updated as 4 and 8. Following subgraph shows vertices and their key values, only the vertices with finite key values are shown. The vertices included in MST are shown in green color. The vertex 1 is picked and added to mstSet. Update the key values of adjacent vertices of 1.
The key value of vertex 2 becomes 8. We can either pick vertex 7 or vertex 2, let vertex 7 is picked. Update the key values of adjacent vertices of 7. The key value of vertex 6 and 8 becomes finite 1 and 7 respectively. Vertex 6 is picked. Update the key values of adjacent vertices of 6.
The key value of vertex 5 and 8 are updated. We repeat the above steps until mstSet includes all vertices of given graph. Finally, we get the following graph. How to implement the above algorithm? We use a boolean array mstSet[] to represent the set of vertices included in MST. If a value mstSet[v] is true, then vertex v is included in MST, otherwise not.
Array key[] is used to store key values of all vertices.
0コメント