Ҷустуҷӯи паҳноӣ (BFS)

Дар бораи ҷустуҷӯи паҳноӣ-аввал (BFS) омӯзед

Муқаддима

Алгоритми ҷустуҷӯи паҳноӣ (BFS) дар графи бевазн кор мекунад ва аз қуллаи манбаъ $s$ оғоз мешавад.

Граф метавонад ҳам самтдор ва ҳам бесамт бошад — BFS дар ҳар ду ҳолат кор мекунад.

Роҳи хуби тасаввур кардани BFS ҳамчун паҳншавии оташ дар граф аст:

• дар қадами $0$, танҳо қуллаи манбаъ $s$ “месӯзад”;
• дар ҳар қадами навбатӣ, оташ аз ҳамаи қуллаҳои ҳоло сӯхта ба ҳамсояҳои онҳо паҳн мешавад.

Пас дар як итератсия, “ҳалқаи оташ” бо як канор васеъ мешавад. Маҳз барои ҳамин BFS қуллаҳоро бо тартиби афзояндаи масофа аз манбаъ боздид мекунад.

Ғоя

Барои татбиқи BFS, мо истифода мебарем:

• як навбат q, ки қуллаҳои барои коркардро нигоҳ медорад;
• массиви used[x], ки нишон медиҳад оё қуллаи x аллакай боздид шудааст ё не.

Дар оғоз:

• қуллаи манбаъ s-ро ба навбат мегузорем;
• онро ҳамчун боздидшуда қайд мекунем;
• ҳамаи қуллаҳои дигарро ҳамчун боздиднашуда қайд мекунем.

Сипас, то вақте ки навбат холӣ нест:

1. қуллаи дар пеши навбат бударо мегирем;
2. аз ҳамаи ҳамсояҳои он мегузарем;
3. агар ҳамсоя ҳанӯз боздид нашуда бошад, онро ҳамчун боздидшуда қайд мекунем ва ба навбат мегузорем.

Дар охири алгоритм, ҳамаи қуллаҳое, ки аз s дастрасанд, боздид мешаванд.

Роҳҳои кӯтоҳтарин

Яке аз муҳимтарин хосиятҳои BFS ин аст, ки дар графи бевазн, он роҳи кӯтоҳтарин-ро аз манбаъ то ҳар қуллаи дастрас меёбад.

Барои ин, мо метавонем нигоҳ дорем: