Ҷустуҷӯи амиқ-аввал (DFS)

Ҷустуҷӯи амиқ-аввал (DFS)-ро омӯзед

Муқаддима

Ҷустуҷӯи амиқ (DFS) яке аз алгоритмҳои асосӣ барои кор бо графҳо мебошад.

Ғояи асосии DFS ин аст, ки аз қуллаи ҷорӣ то ҳадди имкон амиқ равад ва танҳо вақте баргардад, ки дигар қуллаҳои ҳамсояи боздиднашуда намонанд.

Он чӣ гуна кор мекунад?

Мо аз як қулла оғоз мекунем. Пас аз боздиди он, мо ба таври рекурсивӣ DFS-ро барои ҳар як қуллаи ҳамсояе, ки ҳанӯз боздид нашудааст, иҷро мекунем. Бо ин роҳ, мо ҳамаи қуллаҳои дастрас аз қуллаи оғозиро боздид мекунем.

Таснифи канорҳои граф

Ҳангоми иҷрои DFS, канорҳоро метавон бо истифода аз вақтҳои воридшавӣ ва баромадии нӯгҳои онҳо тасниф кард.

Ин тасниф аксар вақт дар масъалаҳои графӣ муфид аст.

Фарз мекунем DFS канори $(x, y)$-ро коркард мекунад.

1. Агар қуллаи $y$ ҳанӯз боздид нашуда бошад

• Канори дарахтӣ — канори $(x, y)$ канори дарахтӣ номида мешавад, агар DFS аз он гузашта, $$-ро бори аввал боздид кунад.