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

Power rule, Power rule: d(x n )/dx = nx n-1 There are really three ...

Power rule: d(x n )/dx = nx n-1 There are really three proofs which we can provide here and we are going to suffer all three here therefore you can notice all of them. T

Confidence interval, Confidence Interval The interval estimate or a 'co...

Confidence Interval The interval estimate or a 'confidence interval' consists of a range as an upper confidence limit and lower confidence limit whether we are confident that a

Statistics, if the sum of mean and variance of a binomial distribution is ...

if the sum of mean and variance of a binomial distribution is 4.8 for five trials, the distribution

Steps for radio test - sequences and series, Steps for Radio test Assum...

Steps for Radio test Assume we have the series ∑a n Define, Then, a. If L b. If L>1 the series is divergent. c. If L = 1 the series might be divergent, this i

Linear Equations of Parallel Lines, A line has the equation 2y=-3x+1. Find...

A line has the equation 2y=-3x+1. Find an equation of a line parallel to this line that has a y-intercept of -2.

How many miles did she average per day, Katie ran 11.1 miles over the last ...

Katie ran 11.1 miles over the last three days. How many miles did she average per day? To ?nd out the average number of miles, you should divide the total number of miles throu

Find out a vector that is orthogonal to the plane, A plane is illustrated b...

A plane is illustrated by any three points that are in the plane.  If a plane consists of the points P = (1, 0,0) , Q = (1,1,1) and R = (2, -1, 3) find out a vector that is orthogo

How many teachers are there at russell high, There are 81 women teachers at...

There are 81 women teachers at Russell High. If 45% of the teachers in the school are women, how many teachers are there at Russell High? Use the proportion part/whole = %/100.

Solve the form ax2 - bx - c factoring polynomials, Solve the form ax 2 - b...

Solve the form ax 2 - bx - c factoring polynomials ? This tutorial will help you factor quadratics that look something like this: 2x 2 -3x - 14 (Leading coefficient is

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