Լայնությամբ որոնման ալգորիթմը

Լայնությամբ որոնումը յուրաքանչյուր գագաթ $v$‍-ին տալիս է երկու արժեք․

Եթե սկզբնական գագաթից դեպի $v$‍ գագաթը ճանապարհ չկա, ապա $v$‍-ի հեռավորությունն անվերջ է, և իր նախորդն ունի նույնքան հատուկ արժեք, որքան սկզբնականի նախորդը։

Օրինակ՝ ահա ուղղություն չունեցող գրաֆիկ, որն ունի ութ գագաթ՝ համարակալված 0-ից 7, որոնք գագաթների վերևում կամ ներքևում են։ Գագաթներից յուրաքանչյուրի ներսում գրված է երկու թիվ՝ հեռավորությունն առաջնային գագաթից, որը գագաթ 3-ն է, և այն նախորդ գագաթի համարը, որով ամենակարճ ճանապարհն է դեպի առաջնային գագաթը՝ 3\ -ը։ Գիծը null արժեքն է․

Լայնությամբ որոնման ժամանակ մենք սկզբում բոլոր գագաթների հեռավորությանն ու նախորդին վերագրում ենք null։ Որոնումը սկսում ենք առաջնային գագաթից ու հեռավորությունը նշանակում 0։ Հետո անցնում ենք դրա բոլոր հարևանների մոտ և ամեն հարևանի հեռավորությունը նշանակում 1, իսկ նախորդը՝ առաջնային գագաթ։ Հետո անցնում ենք 1 հեռավորություն ունեցող և դեռ չայցելած գագաթների հարևանների մոտ և այդ գագաթների հեռավորությունը նշանակում 2, իսկ նախորդը՝ այն գագաթը, որից այցելել ենք այդտեղ։ Այդպես շարունակում ենք, մինչև այցելենք բոլոր գագաթները, և դրանք հասանելի կլինեն սկզբնական գագաթից՝ միշտ այցելելով $k$‍ հեռավորությամբ գագաթը $k+1$‍-ն այցելելուց առաջ։

Արի քայլ առ քայլ անցնենք վերևի օրինակով, իսկ հետո նայենք դրա պատկերավոր տեսքը․

Ուշադրություն դարձրու, որ գագաթ 3-ից դեպի գագաթ 7-ը ճանապարհ չկա, և որոնումը երբեք չի այցելում գագաթ 7։ Հետևաբար, այդ գագաթի հեռավորության ու նախորդի null արժեքները մնում են անփոփոխ։

Մի քանի հարց է առաջանում։ Նախ՝ ինչպես հասկանալ, թե գագաթն արդեն այցելել ենք, թե ոչ։ Սա հեշտ է․ եթե գագաթի հեռավորությունը null է, ապա այն դեռ չենք այցելել։ Հետևաբար, երբ ստուգում ենք գագաթի հարևանները, այցելում ենք միայն այն հարևաններ, որոնց հեռավորությունն այդ պահին null է։

Մյուս հարցն է՝ ինչպես հաշվել, թե որ գագաթներն ենք արդեն այցելել։ Օգտագործում ենք հերթականություն. դա տվյալների կառուցվածք է, որը թույլատրում է ավելացնել և ջնջել տարրեր, որտեղ ջնջված տարրն այդտեղ ամենաերկար մնացած տարրն է։ Այս օրինաչափությունն անվանում ենք առաջինը ներս, առաջինը դուրս։ Հերթականությունն ունի երեք գործողություն․

Գագաթն այցելելիս այն ներմուծում ենք հերթականության մեջ։ Սկզբում ներմուծում ենք առաջնային գագաթը, քանի որ այն մեր այցելած առաջին գագաթն է լինելու։ Որոշելու համար, թե հաջորդը որ գագաթն ենք այցելում, ընտրում ենք հերթականության մեջ ամենաերկարը մնացած օբյեկտն ու հանում ենք հերթականության միջից․ այլ կերպ ասած՝ օգտագործում ենք dequeue()-ով վերադարձրած գագաթը։ Մեր գրաֆի օրինակում այսպիսի տեսքի կլինի հերթականությունը յուրաքանչյուր քայլին, նաև նորից կտեսնես այդ քայլերը պատկերավոր տեսքով․

Ուշադրություն դարձրու, որ ամեն քայլին հերթականության մեջ կան կամ բոլորը նույն հեռավորությամբ գագաթներ, կամ $k$‍ հեռավորությամբ գագաթներ, որոնց հաջորդում են $k+1$‍ հեռավորությամբ գագաթները։ Այդպես ենք մենք համոզվում, որ այցելել ենք բոլոր $k$‍ հեռավորությամբ գագաթները, մինչև կանցնենք $k+1$‍-ներին։

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