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

30-60-90 degree triangle, : Find the length of the hypotenuse of a right tr...

: Find the length of the hypotenuse of a right triangle if the lengths of the other two sides are both 3 inches.

Polynomials, zeroes of polynomial 2x2-3x-2

zeroes of polynomial 2x2-3x-2

Operations with rational numbers, larry spends 3/4 hours twice a day walkin...

larry spends 3/4 hours twice a day walking and playing with his dog. He spends 1/6 hours twice a day feeding his dog. how much time does larry spend on his dog each day?

Find the area of shaded region, Find the area of shaded region, if the side...

Find the area of shaded region, if the side of square is 28cm and radius of the sector is ½ the length of side of square.

Concurrent deviation method, Normal 0 false false false ...

Normal 0 false false false EN-IN X-NONE X-NONE

Mensuration, if area of a rectangle is 27 sqmtr and it perimeter is 24 m fi...

if area of a rectangle is 27 sqmtr and it perimeter is 24 m find the length and breath#

Pair of straight line, show that one of the straight lines given by ax2+2hx...

show that one of the straight lines given by ax2+2hxy+by2=o bisect an angle between the co ordinate axes, if (a+b)2=4h2

Algebra, Manuel is a cross-country runner for his school’s team. He jogged ...

Manuel is a cross-country runner for his school’s team. He jogged along the perimeter of a rectangular field at his school. The track is a rectangle that has a length that is 3 tim

What is set, What is a set? Explain various methods to represent a set in s...

What is a set? Explain various methods to represent a set in set theory. Define the following with the help of suitable examples.      (i) Singleton Set

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