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

Slope of tangent line, Slope of Tangent Line : It is the next major interp...

Slope of Tangent Line : It is the next major interpretation of the derivative. The slope of the tangent line to f ( x ) at x = a is f ′ ( a ) . Then the tangent line is given by,

Toplogy, Let 0 ! V1 !    ! Vk ! 0 be a long exact sequence of vector spa...

Let 0 ! V1 !    ! Vk ! 0 be a long exact sequence of vector spaces with linear maps. Show that P (??1)i dim Vi = 0.

Series solution, Find the series solution of2x2y”+xy’+(x2-3)Y=0 about regul...

Find the series solution of2x2y”+xy’+(x2-3)Y=0 about regular singular point

Matrix, how to solve for x

how to solve for x

Multiple integrals, how to convert double integral into polar coordinates a...

how to convert double integral into polar coordinates and change the limits of integration

Math Help, 1. Which of the following is greater than 4.3 x 10^9 a. 2.1 x ...

1. Which of the following is greater than 4.3 x 10^9 a. 2.1 x 10^9 b. 3.2 x 10^9 c. 5.3 x 10^9 d. 7.4 x 10^8 2. Which of the following is less than 6.5 x 10^-5 a. 1.4 x 10

Integration, how to find area under a curve?

how to find area under a curve?

Calculate latest triangular area sail for his boat, Rick is order a latest ...

Rick is order a latest triangular sail for his boat. He needs knowing the area of the sail. Which formula will he use? The area of a triangle is 1/2 times the length of the bas

Definition of natural exponential function, Definition of Natural exponenti...

Definition of Natural exponential function:   The natural exponential function is f( x ) = e x   where, e= 2.71828182845905........ . Hence, since e > 1 we also know that e x

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