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

Briefly explain markov chains, Question 1 An experiment succeeds twice as ...

Question 1 An experiment succeeds twice as often as it fails. Find the chance that in the next six trials there will be at least four successes Question 2 An insurance compan

What is a lattice, What is a lattice? Which of the following graphs are lat...

What is a lattice? Which of the following graphs are lattice and why? Ans:  Let (L, ≤) be a poset. If each subset {x, y} consisting of any two elements of L, comprises a glb (I

Integration, why we study integration..?? uses

why we study integration..?? uses

Contravariant vector, Ask question #suppose that components of a contravari...

Ask question #suppose that components of a contravariant vector A^i (for n=3)in the coordinate system (x^1,x^2,...,x^n) are A=x,A=y,A=z.Find the components A^p of the vector in the

Homogeneous system , Provided a homogeneous system of equations (2), we wil...

Provided a homogeneous system of equations (2), we will have one of the two probabilities for the number of solutions. 1.   Accurately one solution, the trivial solution 2.

Build upon the childs background with maths, BUILD UPON THE CHILDS BACKGROU...

BUILD UPON THE CHILDS BACKGROUND :  As you read in previous, each child is unique. Individual children vary in age, level of cognition, background, etc. What implications does thi

Julie had $500 how much money did julie spend, Julie had $500. She spent 20...

Julie had $500. She spent 20% of it on clothes and then 25% of the remaining money on CDs. How much money did Julie spend? Find out 20% of $500 by multiplying $500 by the decim

Calculate the area and perimeter of a parallelogram, Calculate the area and...

Calculate the area and perimeter of a parallelogram: Calculate the area and perimeter of a parallelogram with base (b) = 4´, height (h) = 3´, a = 5´ and b = 4´.  Be sure to in

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