Write prim's algorithm, Mathematics

Assignment Help:

Write Prim's Algorithm.  

Ans: Prim's algorithm to find out a minimum spanning tree from a weighted graph in step by step form is given below. 

Let G = (V, E) be graph and S = (VS, ES) be the spanning tree to be found from G.

Step 1: Choose a vertex v1 of V and initialize 

VS = {v1} and

ES

= {}

Step 2: Choose a nearest neighbor of vi from V that is adjacent to some vj∈VS and that edge (vi, vj) does not form a cycle with members edge of ES. Set

VS = VS ∪{vi} and

ES = ES ∪{(vi, vj)}  

Step 3: Again Repeat step2 until |Es| = |V| - 1.


Related Discussions:- Write prim's algorithm

Determine the mean of the subsequent numbers, Determine the mean of the sub...

Determine the mean of the subsequent numbers: Example: Determine the mean of the subsequent numbers: 5, 7, 1, 3, 4 Solution: where x'          =

One integer is two more than another what is greater integer, One integer i...

One integer is two more than another. The sum of the lesser integer and double the greater is 7. What is the greater integer? Let x = the greater integer and y = the lesser int

Maximum and minimum values, Find all the local maximum and minimum values a...

Find all the local maximum and minimum values and saddle points of the function f(x, y) = x 2 - xy + y 2 + 9x - 6y + 10

Convergence, Assume that (xn) is a sequence of real numbers and that a, b €...

Assume that (xn) is a sequence of real numbers and that a, b € R with a is not eaqual to 0. (a) If (x n ) converges to x, show that (|ax n + b|) converges to |ax + b|. (b) Give

Rank correlation coefficient, Rank Correlation Coefficient Also ident...

Rank Correlation Coefficient Also identified as the spearman rank correlation coefficient, its reasons is to establish whether there is any form of association among two vari

Probability, I don''t understand the AND/OR rules and how they apply to pro...

I don''t understand the AND/OR rules and how they apply to probability

Transforming the base of logarithms, Suppose that we know the logarit...

Suppose that we know the logarithms of all numbers which are expressed to base 'a' and we are required to find the logarithms of all these numbers to base 'b'. We

Determine the approximate raw act score, Using the same mean and standard d...

Using the same mean and standard deviation as mean m = 20.1 and a standard deviation s = 5.8. Joe was informed that he scored at the 68 th percentile on the ACT, what was Joe's ap

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd