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

Define euler circuit and euler path, Define Euler Circuit and Euler Path.  ...

Define Euler Circuit and Euler Path.  Which of the following graphs have an Euler circuit and Euler path.

Integration, why we study integration..?? uses

why we study integration..?? uses

Word problems, if I read 6 hours of spring break how many minutes did ...

if I read 6 hours of spring break how many minutes did read

Example of graphical technique of linear equations, Explain the Graphical T...

Explain the Graphical Technique of Linear Equations by using this figure.

Pumping lemma for context free languages, 1. Construct a grammar G such tha...

1. Construct a grammar G such that L(G) = L(M) where M is the PDA in the previous question. Then show that the word aaaabb is generated by G. 2. Prove, using the Pumping Lemma f

Venm diagrams, In a class, all pupils take Mathematics (M), 18 take Chemist...

In a class, all pupils take Mathematics (M), 18 take Chemistry (C), 17 take Biology (B) and 24 take Physics (P) of those taking 3 subjects only, 5 take Physics and Chemistry, 7 ta

What is the surface area of a ball with a diameter of 6 inch, The formula f...

The formula for the surface area of a sphere is 4πr 2 . What is the surface area of a ball with a diameter of 6 inches? Round to the nearest inch. (π = 3.14) If the diameter  o

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