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

GEOMETRIC PROGRESSION, THE FIRST AND THIRD TERM OF A G.P ARE 8 AND 18 RESPE...

THE FIRST AND THIRD TERM OF A G.P ARE 8 AND 18 RESPECTIVELY AND THE COMMON RATIO IS POSITIVE.FIND THE COMMON RATIO

profit & loss, A sell a watch to B at gain of 20% and B sell to C at loss ...

A sell a watch to B at gain of 20% and B sell to C at loss of 10%. if C pays @ 432, how much did A pays for it.

Graphing , what effect is the constant in an equation have on an graph

what effect is the constant in an equation have on an graph

Harmonic mean-arthmetic geometric progression, Harmonic mean It is a m...

Harmonic mean It is a measure of central tendency which is utilized to determine the average increase rates for natural economies. This is defined like the reciprocal of the a

#titlealgebra.., help solve these type equations.-4.1x=-4x+4.5

help solve these type equations.-4.1x=-4x+4.5

Find the number of ways to arrange words, Q. Find the number of ways three ...

Q. Find the number of ways three letter "words" can be chosen from the alphabet if none of the letters can be repeated? Solution:  There are 26 ways of choosing the first lett

Evaluate limit in indeterminate form, Evaluate following limits. S...

Evaluate following limits. Solution In this case we also contain a 0/0 indeterminate form and if we were actually good at factoring we could factor the numerator & den

Marketing research, project assignment of page no.19 question no.2

project assignment of page no.19 question no.2

the jetstream''s speed, A passenger jet took 3 hours to fly 1800 km in the...

A passenger jet took 3 hours to fly 1800 km in the direction of the jetstream. The return trip against the jetstream took four hours. What was the jet's speed in still air and the

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