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

Որքա՞ն ժամանակում է լայնությամբ որոնումն աշխատում $V$V գագաթների խմբով ու $E$E կողերի խմբով գրաֆիկի վրա։ Պատասխանը $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis է։

Արի տեսնենք, թե ինչ է նշանակում $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis ժամանակը։ Մի պահ ընդունիր, որ $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, ինչը բազում գրաֆիկներում այդպես է, հատկապես նրանց դեպքում, որոնց վրա աշխատեցնում ենք լայնության որոնում։ Հետևաբար, $|V| + |E| \leq |E| + |E| = 2 \cdot |E|$vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, E, vertical bar, plus, vertical bar, E, vertical bar, equals, 2, dot, vertical bar, E, vertical bar։ Քանի որ ասիմպտոտային նշագրման մեջ անտեսում ենք հաստատուն գործակիցները, տեսնում ենք, որ երբ $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, ապա $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis-ն նույնն է, ինչ եթե գրենք $O(E)$O, left parenthesis, E, right parenthesis։ Սակայն եթե ունենք $|E| < |V|$vertical bar, E, vertical bar, is less than, vertical bar, V, vertical bar, ապա $|V| + |E| \leq |V| + |V| = 2 \cdot |V|$vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, V, vertical bar, plus, vertical bar, V, vertical bar, equals, 2, dot, vertical bar, V, vertical bar, և այդպիսով $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis-ն նույնն է, ինչ գրենք $O(V)$O, left parenthesis, V, right parenthesis։ Երկու դեպքերը կարող ենք միացնել ու ասել, որ $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis-ն իրականում նույնն է, ինչ եթե գրենք $O(\max(V,E))$O, left parenthesis, \max, left parenthesis, V, comma, E, right parenthesis, right parenthesis։ Ընդհանուր առմամբ, եթե ունենք $x$x ու $y$y պարամետրեր, ապա $O(x+y)$O, left parenthesis, x, plus, y, right parenthesis-ը նշանակում է $O(\max(x,y))$O, left parenthesis, \max, left parenthesis, x, comma, y, right parenthesis, right parenthesis։

(Ուշադրույթուն դարձրու, որ գրաֆիկը միացած է, եթե յուրաքանչյուր գագաթից դեպի մյուս բոլորը ճանապարհ կա։ Կողերի նվազագույն քանակը, որ գրաֆիկը կարող է ունենալ և միևնույն ժամանակ լինել միացած, $|V|-1$vertical bar, V, vertical bar, minus, 1 է։ Գրաֆիկը, որտեղ $|E| = |V|-1$vertical bar, E, vertical bar, equals, vertical bar, V, vertical bar, minus, 1, կոչվում է ազատ ծառ)։

Ինչպե՞ս է լայնությամբ որոնումն աշխատում $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis ժամանակում։ Յուրաքանչյուր գագաթի հեռավորությունն ու նախորդը գտնելու ժամանակը $O(V)$O, left parenthesis, V, right parenthesis է (իրականում՝ $\Theta(V)$\Theta, left parenthesis, V, right parenthesis)։ Յուրաքանչյուր գագաթին այցելում ենք առավելագույնը մեկ անգամ, որովհետև միայն սկզբում է դրա հեռավորությունը null, հետևաբար յուրաքանչյուր գագաթը հերթում լինում է միայն մեկ անգամ։ Քանի որ կողերի վրայով անցնում ենք միայն համապատասխան գագաթների վրայով այցելելիս, ամեն կողի վրայով անցնում ենք առավելագույնը երկու անգամ։ Հետևաբար, լայնությամբ որոնումով գագաթներին այցելում ենք $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis ժամանակում։

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