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

Mortgages, compute the monthly payment on a 30 year level payment mortagage...

compute the monthly payment on a 30 year level payment mortagagesasuming an annual mortgages principal of $400000

Linear programming, what is the advantage of dual linear problem programmin...

what is the advantage of dual linear problem programming when we maximize profit then what is need to minimize cost of the same problem

Algebraic word problems, Algebraic Word Problems: Equations: 1....

Algebraic Word Problems: Equations: 1. The total electrical output of one nuclear facility is 200 megawatts more than that of another nuclear facility. Let L be the

Homotopy, prove same homotopy type is an equivalent relation

prove same homotopy type is an equivalent relation

Linear independence and dependence, It is not the first time that we've loo...

It is not the first time that we've looked this topic. We also considered linear independence and linear dependence back while we were looking at second order differential equation

I NEED HELP, Teng is designing a house and in each room he can choose from ...

Teng is designing a house and in each room he can choose from tiles, floorboards, or carpet for the floor. a. How many combinations of flooring materials are possible if he designs

Area between curves, Area between Curves In this section we will be fi...

Area between Curves In this section we will be finding the area between two curves. There are in fact two cases that we are going to be looking at. In the first case we des

Determine the general solution reduction of order, Determine the general so...

Determine the general solution to 2t 2 y'' + ty' - 3y = 0 It given that y (t) = t -1 is a solution.  Solution Reduction of order needs that a solution already be iden

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