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

Discrete math, ) Show that the following argument is valid: (~p ? q) =>...

) Show that the following argument is valid: (~p ? q) => r s ? ~q ~t p => t (~p ? r) => ~s ------------------------ ? ~q 2) Show that the following argum

Trigonometry identity, if x+y+z=pi=180 prove that sin^2x+sin^2y+sin^z-2sinx...

if x+y+z=pi=180 prove that sin^2x+sin^2y+sin^z-2sinx*siny*sinz=2

Evaluate the slope of the tangent line, Evaluate the given limits, showing ...

Evaluate the given limits, showing all working: Using first principles (i.e. the method used in Example 1, Washington 2009, Using definition to find derivative ) find the

Find the angle of elevation, A 50-foot pole casts a shadow on the ground. ...

A 50-foot pole casts a shadow on the ground. a) Express the angle of elevation θ of the sun as a function of the length s of the shadow. (Hint you may wish to draw this firs

Using pythagorean theorem solve z 2 = ( x + y )2 + 3502, Two people on bik...

Two people on bikes are at a distance of  350 meters.  Person A begin riding north at a rate of 5 m/sec and 7 minutes later on Person B begin riding south at 3 m/sec.  Determine th

Fractions, question paper on fractions

question paper on fractions

Sketch the graph of the derivative of this function f '( x), Below is the s...

Below is the sketch of a function f ( x ) . Sketch the graph of the derivative of this function f ′ ( x ) . Solution : At first glance it seems to an all however impossib

Find var (3x+8) where x is a random variable, If Var(x) = 4, find Var (3x+8...

If Var(x) = 4, find Var (3x+8), where X is a random variable. Var (ax+b) = a 2 Var x Var (3x+8) = 3 2 Var x = 36

What is approximation, approximate value is the precise or the accurate val...

approximate value is the precise or the accurate value which is measured  to the actual value.., approximation is how close the measured value is to the actual value , for example

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