تحلیل و بررسی الگوریتم کروسکال

عمل اصلی: یک دستور مقایسه.

اندازه ورودی : n ، تعداد رئوس و m  تعداد یال ها.

نکته: الگوریتم کروسکال همواره یک درخت پوشای کمینه تولید می کند.

 

اثبات : اثبات از طریق استقرا با شروع از مجموعه ای تهی از یال ها آغاز می شود.

 

void kruskal ( int n , int m,set _ of _ edges E,set _ of _edges & F )
index i , j ;
set _pointer p , q;
edge e ;
sort the m edges in E by weight in
nondecreasing order;
F = Ø ;
intitial (n) ;
while( number of edges in F is less than n-1){
e = edge with least weight not yet
considered ;
i , j = indices of vertices connected by e;
p = find (i) ;
q = find (i) ;
if (! equal ( p, q )) {
merge ( p , q ) ; add e to F ;
}