Algorithm:
Assume :
V is the vertices .
P is the all path in the main graph .
T is the set of edges in MST if graph .
Version 1:
1- start .
2-Read V and P.
3-if ( number of V > 2)
Goto step 4.
Else
the graph is not implementation in this technique
goto step
4- Initial state :
(empty set) A - T=
B- sort the edges in G in Ascending order with respect to cost(weight).
5-While MST is not spanning:
A- let e be the next edge in the sorted list of edge.
B-If (e makes a cycle with edge in T)
Then skip it .
Else Add it to T .(T=TUe).
Return T.
6- print T.
7- stop.
Version 2:
Algorithm :
1- start .
2- Read V and P.
3- Initial state:
A- sort the edges in G in Ascending order with respect to cost.
B-Let Vs={{V1},{V2}....{Vn}}.
Where n=number of vertices .
Vs (sets of vertices).
4-Reapate until Vs Becomes one set holding all Vi:
Where i=1 To number of vertices .
A-Let (Vj,Vk) be the next edge in the sorted list of edges .
V. Where Vj,Vk
Yi (Yi any subset of set Vs ) B- If {Vj,Vk}
Then skip this edge .(because it makes acycle )
Else Yi=Yi U { Vj,Vk }.
Return Yi.
5-print Yi.
6-stop.
For Example:
The solving
Initial state : sorting .
(V1,V7)=1. (V4,V7)=17
(V3,V4)=3 (V1,V2)=20
(V2,V7)=4 (V1,V6)=23
(V3,V7)=9 (V5,V7)=25
(V2,V3)=15 (V5,V6)=28
(V4,V7)=16 (V6,V7)=36
Cost of this spanning tree=57.
وجزاكم الله خير ..