If you're seeing this message, it means we're having trouble loading external resources on our website.

Եթե գտնվում ես վեբ զտիչի հետևում, խնդրում ենք համոզվել, որ *.kastatic.org և *.kasandbox.org տիրույթները հանված են արգելափակումից։

Հիմնական նյութ

Լայնությամբ որոնման վերլուծություն

Որքա՞ն ժամանակում է լայնությամբ որոնումն աշխատում V գագաթների խմբով ու E կողերի խմբով գրաֆիկի վրա։ Պատասխանը O(V+E) է։
Արի տեսնենք, թե ինչ է նշանակում O(V+E) ժամանակը։ Մի պահ ընդունիր, որ |E||V|, ինչը բազում գրաֆիկներում այդպես է, հատկապես նրանց դեպքում, որոնց վրա աշխատեցնում ենք լայնության որոնում։ Հետևաբար, |V|+|E||E|+|E|=2|E|։ Քանի որ ասիմպտոտային նշագրման մեջ անտեսում ենք հաստատուն գործակիցները, տեսնում ենք, որ երբ |E||V|, ապա O(V+E)-ն նույնն է, ինչ եթե գրենք O(E)։ Սակայն եթե ունենք |E|<|V|, ապա |V|+|E||V|+|V|=2|V|, և այդպիսով O(V+E)-ն նույնն է, ինչ գրենք O(V)։ Երկու դեպքերը կարող ենք միացնել ու ասել, որ O(V+E)-ն իրականում նույնն է, ինչ եթե գրենք O(max(V,E))։ Ընդհանուր առմամբ, եթե ունենք x ու y պարամետրեր, ապա O(x+y)-ը նշանակում է O(max(x,y))։
(Ուշադրույթուն դարձրու, որ գրաֆիկը միացած է, եթե յուրաքանչյուր գագաթից դեպի մյուս բոլորը ճանապարհ կա։ Կողերի նվազագույն քանակը, որ գրաֆիկը կարող է ունենալ և միևնույն ժամանակ լինել միացած, |V|1 է։ Գրաֆիկը, որտեղ |E|=|V|1, կոչվում է ազատ ծառ
Ինչպե՞ս է լայնությամբ որոնումն աշխատում O(V+E) ժամանակում։ Յուրաքանչյուր գագաթի հեռավորությունն ու նախորդը գտնելու ժամանակը O(V) է (իրականում՝ Θ(V))։ Յուրաքանչյուր գագաթին այցելում ենք առավելագույնը մեկ անգամ, որովհետև միայն սկզբում է դրա հեռավորությունը null, հետևաբար յուրաքանչյուր գագաթը հերթում լինում է միայն մեկ անգամ։ Քանի որ կողերի վրայով անցնում ենք միայն համապատասխան գագաթների վրայով այցելելիս, ամեն կողի վրայով անցնում ենք առավելագույնը երկու անգամ։ Հետևաբար, լայնությամբ որոնումով գագաթներին այցելում ենք O(V+E) ժամանակում։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: