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

VECTOR, the sum of the vector QR, -SR, TQ and 2ST is?

the sum of the vector QR, -SR, TQ and 2ST is?

Pumping lemma for context free languages, 1. Construct a grammar G such tha...

1. Construct a grammar G such that L(G) = L(M) where M is the PDA in the previous question. Then show that the word aaaabb is generated by G. 2. Prove, using the Pumping Lemma f

Calculate area of a square, The area of a square is given by the formula wi...

The area of a square is given by the formula width time's height. But since the square has all the sides equal, the height is of the same measure as its width. Hence its formula is

volumes for solid of revolution, Volumes for Solid of Revolution Befo...

Volumes for Solid of Revolution Before deriving the formula for it we must probably first describe just what a solid of revolution is. To find a solid of revolution we start o

Index numbers, What are advantages and disadvantages of both Laspeyres and ...

What are advantages and disadvantages of both Laspeyres and Paasche?

Parallelograns, Find x and y in each paarallelogram.

Find x and y in each paarallelogram.

Logarithm, I need help with one logarithm problem

I need help with one logarithm problem

Determine the length of the longer base, The longer base of a trapezoid is ...

The longer base of a trapezoid is 3 times the shorter base. The nonparallel sides are congruent. The nonparallel side is 5 cm more that the shorter base. The perimeter of the trape

Describe graphing equations with a positive slope, Describe Graphing Equati...

Describe Graphing Equations with a Positive Slope? There are 3 steps to graphing a linear equation: 1. Identify and plot the y-intercept. 2. Determine the slope. Use the slope

Standardizing normal variables, Standardizing Normal Variables Suppose ...

Standardizing Normal Variables Suppose we have a normal population. We can represent it by a normal variable X. Further, we can convert any value of X into a corresponding valu

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