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

Show that 3cos-4cos3 = 0, If sin? =  1/2 , show that 3cos?-4cos 3 ? = 0. ...

If sin? =  1/2 , show that 3cos?-4cos 3 ? = 0. Ans:    Sin ? = ½ ⇒ ? = 30 o Substituting in place of ? =30 o . We get 0.

????????, ?????? ?????? ?? ???? ??????? ???????? ?????? 3.5 ?? ??? ???? ???...

?????? ?????? ?? ???? ??????? ???????? ?????? 3.5 ?? ??? ???? ???? ????? 50??/???? ??????20??/???? ???? ?? ?? ?????? ???????? ??? ??? ?? ??????? ??????? ? ?? ????? ????

complex number z, For complex number z, the minimum value of |z| + |z - co...

For complex number z, the minimum value of |z| + |z - cosa - i sina|+|z - 2(cosa + i sina )| is..? Solution) |z| + |z-(e^ia)| + |z-2(e^ia)| we see.....oigin , e^ia , 2e^ia ,  f

Law of cosines - vector, Theorem a → • b → = ||a → || ||b → || cos• ...

Theorem a → • b → = ||a → || ||b → || cos• Proof Let us give a modified version of the diagram above. The three vectors above make the triangle AOB and note tha

.gradient, Draw the graph of y=x^2-4x from x=-1 to x=5.use the scale of 2cm...

Draw the graph of y=x^2-4x from x=-1 to x=5.use the scale of 2cm on the x axis and 1cm on the y axis.Estimate the gradient at point:x=4, x=2 and x=0

Arithmetico geometric progression, find the sum of the following series upt...

find the sum of the following series upto n terms: 1*2+2*4+3*8+4*16+.....

Analyze the dynamic path - difference equation, One of the well-known class...

One of the well-known class of models that involve a simple difference equation are models of mean reversion. These models typically take the form yt+1 - yt = -a(yt - μ)where 0

Circles and cones, length of subnormal to the curve y2=2x+1 at (4,3)

length of subnormal to the curve y2=2x+1 at (4,3)

Probability questions, The probability that a person will get an electric c...

The probability that a person will get an electric contract is 2/5 and the contract that he will not get plumbing  contract is 4/7.If the probability of getting at least one contra

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