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

Need answer!, what is the basic unit of weight in the metric system?

what is the basic unit of weight in the metric system?

Analysis and optimization, 1. In an in finite horizon capital/consumption m...

1. In an in finite horizon capital/consumption model, if kt and ct are the capital stock and consumption at time t, we have f(kt) = ct+kt+1 for t ≥ 0 where f is a given production

Arc length with vector functions - three dimensional space, Arc Length with...

Arc Length with Vector Functions In this part we will recast an old formula into terms of vector functions.  We wish to find out the length of a vector function, r → (t) =

Discrete uniform distribution, Discrete Uniform Distribution Acme Limit...

Discrete Uniform Distribution Acme Limited is a car manufacturer. The company can paint the car in 3 possible colors: White, Black and Blue. Until the population is sampled, th

What is addition rule of probability, Q. What is Addition Rule of probabili...

Q. What is Addition Rule of probability? Ans. Suppose there are 17 girls and 15 boys in your stats class. There are 17 + 15 = 32 ways for your teacher to pick one student

The cost of renting a bike at the local bike is y = 2x + 2, The cost of re...

The cost of renting a bike at the local bike shop can be represented through the equation y = 2x + 2, where y is the total cost and x is the number of hours the bike is rented. Whi

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