Տարբերությունը Կրուսկալի և Պրիմի միջև

2024 Հեղինակ: Alex Aldridge | [email protected]. Վերջին փոփոխված: 2023-12-17 13:41

Kruskal vs Prim

Համակարգչային գիտության մեջ Պրիմի և Կրուսկալի ալգորիթմները ագահ ալգորիթմ են, որը գտնում է միացված կշռված չուղղորդված գրաֆիկի նվազագույն ընդգրկող ծառը: Ընդգրկված ծառը գրաֆի ենթագրաֆն է, որն այնպիսին է, որ գրաֆիկի յուրաքանչյուր հանգույց միացված է ճանապարհով, որը ծառ է: Յուրաքանչյուր տարածվող ծառ ունի կշիռ, և բոլոր ընդգրկող ծառերի նվազագույն հնարավոր կշիռները/արժեքը նվազագույն տարածվող ծառն է (MST):

Ավելին Prim's ալգորիթմի մասին

Ալգորիթմը մշակվել է չեխ մաթեմատիկոս Վոյտեխ Յարնիկի կողմից 1930 թվականին, իսկ ավելի ուշ՝ անկախ համակարգչային գիտնական Ռոբերտ Ք. Պրիմի կողմից 1957 թվականին: Այն վերագտնվել է Էդսգեր Դեյկստրայի կողմից 1959 թվականին: Ալգորիթմը կարող է ներկայացվել երեք հիմնական քայլերով.

Հաշվի առնելով կապակցված գրաֆիկը n հանգույցներով և յուրաքանչյուր եզրի համապատասխան քաշով, 1. Ընտրեք կամայական հանգույց գրաֆիկից և ավելացրեք այն T ծառին (որը կլինի առաջին հանգույցը)

2. Հաշվի առեք ծառի հանգույցներին միացված յուրաքանչյուր եզրի կշիռները և ընտրեք նվազագույնը: Ավելացրե՛ք T ծառի մյուս ծայրում գտնվող ծայրը և հանգույցը և հանե՛ք եզրը գրաֆիկից: (Ընտրեք որևէ մեկը, եթե առկա են երկու կամ ավելի նվազագույններ)

3. Կրկնեք 2-րդ քայլը, մինչև ծառին ավելացվեն n-1 եզրեր:

Այս մեթոդում ծառը սկսվում է մեկ կամայական հանգույցից և ընդլայնվում է այդ հանգույցից յուրաքանչյուր ցիկլով: Հետևաբար, որպեսզի ալգորիթմը ճիշտ աշխատի, գրաֆիկը պետք է լինի միացված գրաֆիկ: Պրիմի ալգորիթմի հիմնական ձևն ունի O(V^{2) ժամանակային բարդություն.}

Ավելին Կրուսկալի ալգորիթմի մասին

Ջոզեֆ Կրուսկալի կողմից մշակված ալգորիթմը հայտնվել է Ամերիկյան մաթեմատիկական ընկերության աշխատություններում 1956 թվականին: Կրուսկալի ալգորիթմը կարող է արտահայտվել նաև երեք պարզ քայլով:

Հաշվի առնելով n հանգույցներով գրաֆիկը և յուրաքանչյուր եզրի համապատասխան քաշը, 1. Ընտրեք ամբողջ գրաֆիկի նվազագույն քաշով աղեղը և ավելացրեք ծառին և ջնջեք գրաֆիկից:

2. Մնացածներից ընտրեք նվազագույն կշռված եզրը, այնպես, որ ցիկլ չձևավորվի: Ծառին ավելացրեք եզրը և ջնջեք գրաֆիկից: (Ընտրեք որևէ մեկը, եթե առկա են երկու կամ ավելի նվազագույններ)

3. Կրկնեք գործընթացը 2-րդ քայլում։

Այս մեթոդում ալգորիթմը սկսվում է նվազագույն կշռված եզրից և շարունակում է ընտրել յուրաքանչյուր եզր յուրաքանչյուր ցիկլում: Հետևաբար, ալգորիթմում գրաֆիկը պետք չէ միացնել: Կրուսկալի ալգորիթմն ունի O(logV) ժամանակային բարդություն

Ո՞րն է տարբերությունը Կրուսկալի և Պրիմի ալգորիթմի միջև:

• Prim-ի ալգորիթմը սկզբնավորվում է հանգույցով, մինչդեռ Կրուսկալի ալգորիթմը մեկնարկում է եզրով:

• Prim-ի ալգորիթմները տարածվում են մի հանգույցից մյուսը, մինչդեռ Կրուսկալի ալգորիթմն ընտրում է եզրերը այնպես, որ եզրի դիրքը հիմնված չէ վերջին քայլի վրա:

• Պրիմի ալգորիթմում գրաֆիկը պետք է լինի միացված գրաֆիկ, մինչդեռ Kruskal-ը կարող է գործել նաև անջատված գրաֆիկների վրա:

• Պրիմի ալգորիթմն ունի O(V^{2), իսկ Կրուսկալի ժամանակային բարդությունը O(logV): է:}