:: Computer Application :: 

Prim's Method

[ Kruskal Method ] [ Prim's Method ] [ Dijkastra’s algorithm ] [ Selection ] [ Predicate Calculus ]

Main Chapters

Home
Introduction to Software
Data Structures
System Engineering
Database Management System
Discrete Mathemarics
Numerical & Statistical Computing
Software Engineering
Operation Research
Acounting & Finance
Computer Architecture
Operating Systems
Intelligent Systems
Relational Database
Obejct Oiented Systems

 

Prim's Method
Question  1:  Find a minimal spanning tree for the connected weighted graph using  Prim's Method
Ans. (i) Prim's Method

Step - 1: Choose a vertex a and then select one of three edges incident with a with minimum weight.
W(ab) = 5
W(af) = 3
W(ae) = 5

So select af.

Step - 2: now we can choose minimum from the following edges.
W(ab) = 5
W(ae) = 5
W(fd) = 5
W(fb) = 6
Select ae.


Step - 3: now we can choose minimum from the following edges incidence on a or e or f.
W(ab) = 5
W(ed) = 7
W(fd) = 8
W(fb) = 6
Select ab.

Step - 4: now we can choose minimum from the following edges incidence on b or e or f.
W(bc) = 4
W(ed) = 7
W(fd) = 8
We have not included edge bf as it makes a cyclic loop as a-f-b
So, select bc.

Step - 4: now we can choose minimum from the following edges incidence on c or e or f.
W(cd) = 9
W(ed) = 7
W(fd) = 8

So, select ed.

Now all the vertices are traversed and this completes the formation of Minimal Spanning Tree.
Total Wt = w (bc + ab + af = ae + ed)
= 5 + 4 + 3 + 5 + 7 = 24

Links for Web Developers Web Publishers

 

Links from Google

 
 
 

[ Up ] [ Kruskal Method ] [ Prim's Method ] [ Dijkastra’s algorithm ] [ Selection ] [ Predicate Calculus ]

This is archive of an MCA course completed by BK Pandey. This is published here for the benefit of all visitors.

- Disclaimer -

These articles may treated as study material and veracity of the materials may be checked by the users. Publisher of this material is not responsible for any mistake or error committed in the programming codes in the respective sections.