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

5th grade, 6 and 3/8 minus 1 and 3/4

6 and 3/8 minus 1 and 3/4

Ryan gym membership costs him how much is every installment, Ryan's gym mem...

Ryan's gym membership costs him $390 per year. He pays this within twelve equal installments a year. How much is every installment? To ?nd out each installment, the total yearl

Shares and dividends, at what price a 6.25%rs 100 share be quoted when the ...

at what price a 6.25%rs 100 share be quoted when the money is worth 5%

Prove that op=2ap, Two tangents PA and PB are drawn to the circle with cent...

Two tangents PA and PB are drawn to the circle with center O, such that ∠APB=120 o . Prove that OP=2AP. Ans:    Given : - ∠APB = 120o Construction : -Join OP To prove : -

Determine the property of join in a boolean algebra, Determine that in a Bo...

Determine that in a Boolean algebra, for any a and b, (a Λ b) V (a Λ b' ) = a.  Ans: This can be proved either by using the distributive property of join over meet (or of mee

Linear equation in two variables., draw the graph of following pair of line...

draw the graph of following pair of linear equation:-2y=4x-6

What is the opec, What is the OPEC? - The Organization of the Petroleum Exp...

What is the OPEC? - The Organization of the Petroleum Exporting Countries, a coordination group of petrol producers The Organization for Peace and Economic Cooperation, a German le

Calculate the volume of rectangular piece of cardboard, 1. A rectangular pi...

1. A rectangular piece of cardboard measuring 15 inches by 24 inches is to be made into a box with an open top by cutting equal size squares from each comer and folding up the side

Write down the first few terms of the sequences, Write down the first few t...

Write down the first few terms of each of the subsequent sequences. 1. {n+1 / n 2 } ∞ n=1 2. {(-1)n+1 / 2n} ∞ n=0 3. {bn} ∞ n=1, where bn = nth digit of ? So

Market, what is market,what is marketing

what is market,what is marketing

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