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

Estimate the position of an object at any time, The position of an object a...

The position of an object at any time t (in hours) is specified by, s (t ) = 2t 3 - 21t 2 + 60t -10 Find out when the object is moving to the right and whiles the object

Sums and differences of cubes and other odd powers, Sums and Differences of...

Sums and Differences of Cubes (and other odd powers)? You can factor a sum or difference of cubes using the formulas a 3 - b 3 = (a - b )(a 2 + ab + b 2 ) and a 3 + b 3 =

Compound interest, you have RM5O,OOO to invest,and two fund that you''d li...

you have RM5O,OOO to invest,and two fund that you''d like to invest in.The You-Risk-It Fund yields 14% interest.The Extra-Dull Fund yields 6% interest.Besause of college financial-

Probability, The probability that a leap year will have 53 sunday is ? and ...

The probability that a leap year will have 53 sunday is ? and how please explain it ? (a)1/7    (b) 2/7    (c) 5/7    (d)6/7 Sol) A leap year has 366 days, therefore 52 weeks i.e

Accumulated amount , $26,000 is spended for two years. In the first year it...

$26,000 is spended for two years. In the first year it gets interest at 8.3% p.a. compounded semi annually. In the same year the rate of interest changes to 7.5% p.a. compounded da

Maximin method -decision making under uncertainty, Decision making under un...

Decision making under uncertainty Various methods are used to make decision in circumstances whereas only the pay offs are identified and the likelihood of every state of natur

Differential equations and group methods, solve the differential equation ...

solve the differential equation dy/dx=f(y)x^n+g(y)x^m by finding a one-parameter group leaving it invariant

Dilemmas of america''s minority groups, Explain this statement " As we begi...

Explain this statement " As we begin the 21st century, the dilemmas of America's minority groups remain perhaps the primary unresolved domestic issue facing the nation." How might

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