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

Evaluate the measure of the larger angle, Two angles are complementary. The...

Two angles are complementary. The calculate of one angle is four times the measure of the other. Evaluate the measure of the larger angle. a. 36° b. 72° c. 144° d. 18°

Derive the probability distribution of the completion times, Derive the pro...

Derive the probability distribution of the completion times: a. The following probability distributions relate to the completion times, in weeks, T A and T B of two independ

Andrew is helping his mom remodel his room, The perimeter of Andrew''s rect...

The perimeter of Andrew''s rectangular room is 44 feet. What equation was used to find the perimeter?

Why did the two dice game become more difficult?, The following exercises m...

The following exercises may help you to look more closely at the activities done above. E1) Why did the two dice game become more difficult? E2) Do you find the activities in

Find the values of k, If the vertices of a triangle are (1, k), (4, -3), (-...

If the vertices of a triangle are (1, k), (4, -3), (-9, 7) and its area is 15 sq units, find the value(s) of k..

Mr, Probability of A is 85% Probability of B is 45% Probability A and B 56%...

Probability of A is 85% Probability of B is 45% Probability A and B 56% What is the probability of not either A or B?

Show that aq= 1/2 perimeter of triangle abc, A circle touches the side BC o...

A circle touches the side BC of a triangle ABC at P and touches AB and AC when produced at Q and R. Show that AQ= 1/2 (perimeter of triangle ABC) Ans:    Since the length o

Volumes of solids of revolution - method of rings, Volumes of Solids of Rev...

Volumes of Solids of Revolution / Method of Rings In this section we will begin looking at the volume of solid of revolution. We have to first describe just what a solid of rev

Draw a common graph f ( x ) = - x2 + 2x + 3 , Graph        f ( x ) = - x 2 ...

Graph        f ( x ) = - x 2 + 2x + 3 . Solution It is a parabola in the general form.                              f ( x ) = ax 2 + bx + c In this form, the x-coor

Example of quadratic polynomial, Factor following.                    x ...

Factor following.                    x 2 - 20 x + 100 Solution In this case we've got three terms & it's a quadratic polynomial.  Notice down as well that the constant

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