Here Appsrex giving you the Algorithm used in finding Minimum spanning tree called as Prim’s Algorithm.
Minimum Spanning Tree is the Tree Structure transformed from a weighted graph, but in this, the Sum of Weights on their edges connecting two vertices, should be minimum.
Prim’s Algorithm is one of the best algorithm for finding Minimum Spanning Tree.
It uses Greedy Approach/Method/Strategy for Transforming Given Graph into Minimum Spanning Tree.
Minimum Spanning Tree is the Tree Structure transformed from a weighted graph, but in this, the Sum of Weights on their edges connecting two vertices, should be minimum.
Prim’s Algorithm is one of the best algorithm for finding Minimum Spanning Tree.
It uses Greedy Approach/Method/Strategy for Transforming Given Graph into Minimum Spanning Tree.
MST- PRIM’S(G,w,r)
u.key = ∞
u.π = ∞
r.key = 0
Q = G.V
While (Q != Φ)
u = EXTRACT-MIN(Q)
For each v ɛ G.Adj[u] do
If (v ɛ Q and w(u,v) < v.key) then
v.π = u
v.key = w(u,v)
Here, u.key -> Means, the weight of edge from 'u' to any vertex 'a'.
u.π -> Means, the predecessor of each vertex.
w(u,v) -> Means, the weight of edge from 'u' to 'v'.
0 comments
If you have any questions or suggestions, you are free to ask, i will appreciate that and, i will try my best...