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

Show that of all right triangles inscribed in a circle, Show that of all ri...

Show that of all right triangles inscribed in a circle, the triangle with maximum perimeter is isosceles.

first and third quartiles, From the data given below calculate the value o...

From the data given below calculate the value of first and third quartiles, second and ninth deciles and forty-fifth and fifty-seventh percentiles.

Illustration of integration by parts - integration technique, Example of In...

Example of Integration by Parts - Integration techniques Some problems could need us to do integration by parts many times and there is a short hand technique that will permit

Mode, What is the median for this problem (55+75+85+100+100)

What is the median for this problem (55+75+85+100+100)

Multiples, The sum of the smallest and largest multiples of 8 up to 60 is?

The sum of the smallest and largest multiples of 8 up to 60 is?

Shares and dividends, to use newspaperto study and report on shares and div...

to use newspaperto study and report on shares and dividend

Calculate the limit of f (-4), Let's take a look at one more example to ens...

Let's take a look at one more example to ensure that we've got all the ideas about limits down that we've looked at in the last couple of sections. Example: Given the below gr

Probability, A man enter a lucky draw that requires him to pick five differ...

A man enter a lucky draw that requires him to pick five different integers from 1 through 30 inclusive .he chooses his five number in such a way that the sum of their log base 10 i

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