Կրուսկալի ալգորիթմ

**Կրուսկալի ալգորիթմը** գրաֆների տեսության մեջ ժլատ ալգորիթմ է, որը փնտրում է նվազագույն ճյուղավորված ծառը կապված կշռված գրաֆի հետ։ Դա նշանակում է, որ այն փնտրում է բնագավառներ, որոնք ձևավորում են ծառ, որը պարունակում է բոլոր գագաթները, որտեղ ծառի բոլոր եզրերի ամբողջական կշիռը նվազագույնն է։ Եթե բոլոր գրաֆները կապված չեն, այն որոնում է *նվազագույն ճյուղավորված անտառը* (նվազագույն ճյուղավորված ծառը յուրաքանչյուր միացված կոմպոնենտի համար).

Այս ալգորիթմը առաջին անգամ հայտնվել է Ամերիկյան Մաթեմատիկական Միության վարույթի ժամանակ 1956 թվականին, և գրվել է Ջոզեֆ Կրուսկալի կողմից.

## Ձևակերպում
* ստեղծել *F* անտառը (մի շարք ծառեր), որտեղ գրաֆի յուրաքանչյուր եզր առանձին ծառ է
* ստեղծել մի շարք *S*, որոնք պարունակում են գրաֆի բոլոր եզրերը 
* մինչ *S*-ը դատարկ չէ և F-ը դեռ ճյուղավորվոծ չէ 
** հեռացնել *S*-ից նվազագույն կշիռ ունեցող ծայրը
** եթե այդ ծայրը պարունակում է երկու տարբեր ծառեր, ապա ավելացնել դա անտառին՝ միավորելով երկու ծառերը որպես մեկ ծառ 
** հակառակ դեպքում անհետացնել այդ ծայրը։
Ալգորիթմի դադարեցման դեպքում անտառը կունենա միայն մեկ կոմպոնենտ և ձևավորի գրաֆի նվազագույն ճյուղավորված ծառը։

## Նկարագրություն
Երբ *E*-ն գրաֆի եզրերի թիվն է և *V*-ն բարձրության թիվը, Կրուսկալի ալգորիթմը կարող է ցույց տալ, որ *[[Big-O notation|O]]*(*E* log *E*) ժամանակում աշխատելը, կամ որ նույնն է՝ *O*(*E* log *V*) ժամանակում, բոլորը պարզ կառուցվածքով տվյալների հետ է։ Այս կատարման ժամանակները հավասարազոր են, որովհետև. 
* *E*-ն ամենամեծ *V*2-ում է և \log V^2 = 2 \log V \; *O*(log *V*) է։
* Եթե մենք անտեսում ենք առանձին բարձրությունները, որոնցից յուրաքանչյուրը կարող է լինել սեփական կոմպոնենտ նվազագույն ճյուղավորված անտառում, *V* ≤ *E*+1, այսպիսով՝ log *V* *O*(log *E*) է։

Մենք կարող ենք հասնել այդ կապվածությանը հետևյալ կերպ. առաջին հերթին տեսակավորենք եզրերը ըստ կշիռների՝ օգտագործելով համեմատության տեսակը *O*(*E* log *E*) ժամանակում, այս քայլը թույլ է տալիս "հեռացնել *S*-ից նվազագույն կշիռ ունեցող եզրը " հաստատուն ժամանակում աշխատելու համար։ Այնուհետև մենք օգտագործում ենք տվյալների չհատվող հավաքածուի կառուցվածքը (Միավորում&Որոնում) վերահսկելու համար, թե որ կոմպոնենտը ինչ բարձրություն ունի։ Մենք պետք է իրականացնենք O(*E*) գործողություններ, երկու 'փնտրման' գործողություններ և մեկ միավորում յուրաքանչյուր եզրի համար։ Նույնիսկ ամենապարզ տվյալների չհատվող հավաքածուի կառուցվածքը, ինչպիսինն են չհատվող անտառները կարող են իրականացնել O(*E*) գործողություններ *O*(*E* log *V*) ժամանակում։ Այնուամենայնիվ ընդհանուր ժամանակը՝ *O*(*E* log *E*) = *O*(*E* log *V*).

Պայմանով, որ եզրերը կամ արդեն տեսակավորված են կամ կարող են տեսակացորված լինել գծային ժամանակում, ալգորիթմը կարող է օգտագործել ավելի բարդ տվյալների չհատվող հավաքածուի կառուցվածք *O*(*E* α(*V*)) ամանակում աշխատելու համար, որտեղ α-ն չափազանց դանդաղ աճող հակադրությունն է Ակերմանի ֆունկցիայի։

## Օրինակ

Բեռնել նմուշ տվյալներ 

## Ստույգության ապացույց

Ապացույցը բաղկացած է երկու մասից։ Առաջինը ապացուցվում է, որ ալգորիթմը ներկայացնում է ճյուղավորված ծառ։ Երկրորդը ապացուցվում է, որ կառուցված ճյուղավորված ծառն ունի նվազագույն կշիռ։

### Ճյուղավորված ծառ
Ենթադրենք ունենք միացված, կշռված P գրաֆ և ենթագրաֆ՝ ներկայացված ալգորիթմի կողմից Y P։ Y-ը չի կարող ունենալ ցիկլ, քանի որ ցիկլին ավելացրած վերջին եզրը կլիներ մեկ ծառի մեջ և ոչ երկու տարբեր ծառերի։ Y-ը չի կարող լինել անջատ, քանի որ առաջինը բախվում է այն եզրին, որը միավորում է Y-ի երկու կոմպոնենտները։ Այսպիսով, Y-ը հանդիսանում է P-ի ճյուղավորված ծառը։

### Նվազագույն
Մենք ցույց տվեցինք, որ հետևյալ ***P*** առաջարկությունը ճիշտ է։ Եթե *F*-ը եզրերի շարք է՝ ընտրված ալգորիթմի ցանկացած փուլում, ապա գոյություն ունի որևէ նվազագույն ճյուղավորված ծառ, որը պարունակում է *F*։
* ***P***-ն ճիշտ է սկզբում, երբ *F*-ը դատարկ է. որևէ նվազագույնճյուղավորված ծառ պետք է լինի, և գույություն ունի մեկը, որովհետև կշռված, միացված գրաֆը միշտ ունի նվազագույն ճյուղավորված ծառ։ 
* Հիմա ենթադրենք, որ ***P***-ն ճիշտ է որոշ ոչ վերջնական *F* եզրի համար և *T*-ն նվազագույն ճյուղավորված ծառն է, որը պարունակում է *F*։ Եթե հաջորդ ընտրված *e* եզրը նույնպես *T*-ում է, ապա ***P***-ն ճիշտ է *F* + *e*-ի համար։ Հակառակ դեպքում, *T* + *e*-ն ունի *C* ցիկլ և կա մեկ այլ՝ *f* եզր, որը *C*-ում է։ (Եթե չլիներ *f* եզրը, ապա *e*-ն չէր կարող ավելացվել *F*-ին, քանի որ դա կստեղծեր *C* ցիկլ։) Ապա *T* &minus; *f* + *e*-ն ծառ է և ունի նույն կշիռը, ինչ *T*-ն, քանի որ *T*-ն ունի նվազագույն կշիռ և *f*-ի կշիռը չի կարող լինել ավելի քիչ, քան *e*-ի կշիռը, հակառակ դեպքում ալգորիթմը կընտրեր *f*-ը *e*-ի փոխարեն։ Այսպիսով, *T* &minus; *f* + *e*-ն նվազագույն ճյուղավորված ծառ է, որը պարունակում է *F* + *e*։
* Հետևաբար, ***P*** -ն իմաստ ունի, երբ *F*-ը դառնում է ճյուղավորված ծառ, որը միայն հնարավոր է, երբ *F*-ը նվազագույն ճյուղավորված ծառ է։

## Աղբյուրներ
* Joseph. B. Kruskal։ *[http://links.jstor.org/sici?sici=0002-9939(195602)7%3A1%3C48%3AOTSSSO%3E2.0.CO%3B2-M On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem]*. In։ *Proceedings of the American Mathematical Society*, Vol 7, No. 1 (Feb, 1956), pp.&nbsp;48–50
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2։ The algorithms of Kruskal and Prim, pp.&nbsp;567&ndash;574.
* Michael T. Goodrich and Roberto Tamassia. *Data Structures and Algorithms in Java*, Fourth Edition. John Wiley & Sons, Inc., 2006. ISBN 0-471-73884-0. Section 13.7.1։ Kruskal's Algorithm, pp.&nbsp;632.

Կատեգորիա:Գրաֆների ալգորիթմներ