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

Calculate time interval, From top of a tower a stone is thrown up and it re...

From top of a tower a stone is thrown up and it reaches the ground in time t1. A second stone is thrown down with the same speed and it reaches the ground in t2. A third stone is r

Determine the area of the walkway, Mark is preparing a walkway around his i...

Mark is preparing a walkway around his inground pool. The pool is 20 by 40 ft and the walkway is intended to be 4 ft wide. Determine the area of the walkway? a. 224 ft 2 b.

Please solve this question, The number of integral pairs (x,y) satisfying t...

The number of integral pairs (x,y) satisfying the equation x^2=y^2+1294 is a)2 b)3 c)4 d)None of these

Functions of several variables - three dimensional space, Functions of Seve...

Functions of Several Variables - Three Dimensional Space In this part we want to go over a few of the basic ideas about functions of much more than one variable. Very first

Determine if r is equivalence relation or a partial ordering, Let R be the ...

Let R be the relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) ∈ R if and only if ad = bc.  Determine whether R is an equivalence relation or a p

Step functions, Before going to solving differential equations we must see ...

Before going to solving differential equations we must see one more function. Without Laplace transforms this would be much more hard to solve differential equations which involve

Solving problem with linear function, An electric utility company determine...

An electric utility company determines the monthly bill for a residential customer by adding an energy charge of 5.72 cents per kilowatt-hour to its base charge of $16.35 per month

Shortricks, shortricks of compound interest

shortricks of compound interest

probability , An engineer has 200 resistors that he keeps in one box. Resi...

An engineer has 200 resistors that he keeps in one box. Resistors are colored to help their identification, and in this box there are 30 white resistors, 50 black resistors, 80 red

Polya’s first and second principle:-mathematical problem, Mathematical Prob...

Mathematical Problem Solving In 1945, mathematician George Polya (1887-1985) published a book titled How To Solve It in which he demonstrated his approach to solving problems.

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