06-09-2016, 10:54 AM
1453185560-primsppt.ppt (Size: 1.79 MB / Downloads: 5)
A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connects all the vertices of G at lowest total cost.
A minimum spanning tree exists if and only if G is connected.
The number of edges in the minimum spanning
tree is |V| - 1.
4. The minimum spanning tree is a tree because it is acyclic.(Cycle formation is not allowed)
PRIM'S ALGORITHM
One way to compute a minimum spanning tree is to grow the tree in successive stages.
In each stage, one node is picked as the root, and we add an edge, and thus an associated vertex, to the tree.
It uses greedy technique.
Steps
Select any vertex
Select the shortest edge connected to that vertex
Select the shortest edge connected to any vertex already connected
Repeat step 3 until all vertices have been connected