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

Find a minimum cost spanning arborescence rooted, Find a minimum cost spann...

Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class.  Please show your work, and also give a final diagram w

Multiply the polynomials, Multiply following. (a) (4x 2 -x)(6-3x) (b)...

Multiply following. (a) (4x 2 -x)(6-3x) (b) (2x+6) 2 Solution  (a) (4x 2 - x )(6 - 3x ) Again we will only FOIL this one out. (4x 2  - x )(6 - 3x) = 24x 2 -

An initial species population , An initial species population is y(0) = 300...

An initial species population is y(0) = 3000. At t=0 the population starts to grow exponentially with a doubling time of 2 years. Mark the only correct statement: a)    The per

Concept, uses of maths concept

uses of maths concept

Definition of logarithms, Q. Definition of Logarithms? Ans. A loga...

Q. Definition of Logarithms? Ans. A logarithm to the base a of a number x is the power to which a is raised to get x. In equation format: If x = a y , then log a  x

Find the volume of a cylinder of radius r, Find the volume of a cylinder of...

Find the volume of a cylinder of radius r and height h. Solution : Here, as we mentioned before starting this illustration we actually don't require using an integral to get t

Algebra function., problem to understand an problem; f(X-2)=X+3 / X-4

problem to understand an problem; f(X-2)=X+3 / X-4

Law of cosines - vector, Theorem a → • b → = ||a → || ||b → || cos• ...

Theorem a → • b → = ||a → || ||b → || cos• Proof Let us give a modified version of the diagram above. The three vectors above make the triangle AOB and note tha

What was the planes average speed, A ?ight from Pittsburgh to Los Angeles t...

A ?ight from Pittsburgh to Los Angeles took 5 hours and covered 3,060 miles. What was the plane's average speed? Find out the rate at that Susan is traveling through dividing h

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