«Փնտրում դեպի լայնություն»–ի խմբագրումների տարբերություն
Content deleted Content added
No edit summary |
No edit summary |
||
Տող 4.
|նկար = [[Image:Breadth-first-tree.svg|none|300px|]]
|տվյալներ = [[Գրաֆ (տվյալների կառուցվածք)|Գրաֆ]]
|տարածք = <!-- <math>O(|V|) = O(b^d)</math> -->
}}
Տող 43.
Q.enqueue(n)
</source>
=== Ավելի մանրամասն ===
Այս ոչ-ռեկուրսիվ ներկայացումը նման է փնտրում դեպի խորության ոչ-ռեկուրսիվ ներկայացմանը, բայց տարբերվում է երկու բանով․
# օգտագործում է հերթ սթեքի փոխարեն
# այն ստուգում է, թե հանգույցը բացահայտվել է, մինչ հերթի մեջ գցվելը, այլ ոչ թե հետաձգում ստուգումը, մինչև գագաթը դուրս կբերեն հերթից։
Յուրաքանչյուր գագաթի (կամ հանգույցի) երկարությունը պետք է, երբ գրաֆի գագաթների միջև փնտրում ենք կարճագույն ճանապարհը։ Ալգորիթմի սկզբում յուրաքանչյուր գագաթի երկարությունը անսահմանություն է, որը ուղակի ցույց է տալիս, որ գագաթը դեռ չի բացահայտվել, այսպիսով այն սկզբնական գագաթից չունի հեռավորություն։ Կարող ենք օգտագործել ուրիշ սիմվոլներ, օրինակ՝ -1:
Յուրաքանչյուր գագաթի ծնող հատկությունը կարող է օգտակար լինել կարճագույն ճանապարհը գտնելու համար:
«NIL»-ը ուղակի սիմվոլ է, որը ցույց է տալիս ինչ-որ բանի բացակայությունը, այս դեպքում ցույց է տալիս ծնող (կամ նապորդի) հանգույցի բացակայությունը, երբեմն, «NIL»-ի փոխարեն օգտագործում են «null», «none» կամ «nothing»։
Նշում, որ հանգույց բառը երբեմն փոխվում է գագաթ բառով։
=== Օրինակ ===
Լայնության ծառի հետևյալ օրինակը ստացվել է՝ կիրառելով փնտրում դեպի լայնություն՝ [[Ֆրանկֆուրտ]]ից։
[[Image:MapGermanyGraph.svg|thumb|250px|center|]]
[[Image:GermanyBFS.svg|thumb|250px|center |]]
== Ծանոթագրություններ ==
{{ծանցանկ}}
| |||