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

Example of one-to-one correspondence, An educator placed 10 pebbles in a ro...

An educator placed 10 pebbles in a row and asked four-year-old Jaswant to count how many there were. She asked him to touch the pebbles .while counting them. Jaswant counted the pe

DETERMINANT, IF 7 AND 2 ARE TWO ROOTS OF THE EQUATION |X 3 7 2 X 2 7 6 X...

IF 7 AND 2 ARE TWO ROOTS OF THE EQUATION |X 3 7 2 X 2 7 6 X |=0 THEN FIND THE THIRD ROOT IS

Erin is painting a bathroom what is the area to be painted, Erin is paintin...

Erin is painting a bathroom along with four walls each measuring 8 ft through 5.5 ft. Ignoring the doors or windows, what is the area to be painted? The area of the room is the

Compute the center of mass of the solid, 1) Compute the center of mass of t...

1) Compute the center of mass of the solid of unit density 1 bounded (in spherical coordinates) by p=1 and by φ is greater than or equal 0 and less than or equal pi/4

Calculate probability, The following table contains some information about...

The following table contains some information about the model used. Assume the probabilities given by the model are those of being a good writer. Variable

Infinite limits, Infinite Limits : In this section we will see limits who...

Infinite Limits : In this section we will see limits whose value is infinity or minus infinity.  The primary thing we have to probably do here is to define just what we mean w

Explain english system in details, Explain English System in details? T...

Explain English System in details? There are three types of measurements that can be taken using the English System: length, distance, weight, and capacity. Length and dista

Area, area of r=asin3x

area of r=asin3x

Correlation and regression, Correlation and Regression Correlation ...

Correlation and Regression Correlation CORRELATION is an important statistical concept which refers to association or interrelationship among variables. The reasons of

Calculate the area of remaining piece of cardboard, A piece of cardboard in...

A piece of cardboard in the shape of a trapezium ABCD & AB || DE, ∠ BCD = 900, quarter circle BFEC is removed. Given AB = BC = 3.5 cm, DE = 2 cm. Calculate the area of remaining p

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