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

Sum, As1212uestion #Minimum 100 words accepted#

As1212uestion #Minimum 100 words accepted#

Solve for x and y liner equation, Solve for x , y (x + y - 8)/2   ...

Solve for x , y (x + y - 8)/2   =( x + 2  y - 14)/3 = (3 x + y - 12 )/ 11   (Ans: x=2, y=6) Ans :     x+ y - 8/2  =   x + 2y - 14 /3  =    3x+ y- 12/11

Which of the following sets are equal, Which of the following sets are equa...

Which of the following sets are equal? S 1 = {1, 2, 2, 3}, S 2 = {x | x 2 - 2x + 1 = 0}, S 3 = {1, 2, 3}, S 4 = {x | x 3 - 6x

find the slope and the y intercept of the line - geometry, 1. Find the slo...

1. Find the slope and the y-intercept of the line whose equation is 5x + 6y = 7. 2. Find the equation of the line that is parallel to 2x + 5y = 7 and passes through the mid poin

Algebraic number, prove that every non-trivial ingetral solution (x,y,z)of ...

prove that every non-trivial ingetral solution (x,y,z)of the diophantine equation Xsquare +Ysquare=Zsquare satisfies gcd(x,y)=gcd(x,z)=gcd(y,z)

Define markov chain, Define Markov chain Random processes with Markov ...

Define Markov chain Random processes with Markov property which takes separate values, whether t is discrete or continuous, are known as Markov chains.

Determine rank correlation coefficient, Determine Rank Correlation Coef...

Determine Rank Correlation Coefficient A group of 8 accountancy students are tested in Quantitative Techniques and Law II.  Their rankings in the two tests were as:

Matrix addition and subtraction, What is Matrix addition and subtraction? I...

What is Matrix addition and subtraction? Illustrate the procedure of Matrix addition and subtraction.

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