BFS - پیاده روی عرض


اولین جستجوی پهنا (BFS)
BFS (جستجوی عرض-اول، جستجوی عرض-اول) - یک روش پیمایش نمودار، که اغلب در الگوریتم های ساده و پیشرفته استفاده می شود. جستجوی Breadth-First با قدم گذاشتن در سطوح جداگانه نمودار، شروع از گره منبع و دور شدن تدریجی از آن کار می کند. این به وضوح در انیمیشن نشان داده شده است.
برای نوشتن ساده ترین BFS ، باید بتوانید با ساختار داده ای کار کنید که به شما امکان می دهد از ابتدا  بردارید و آن را تا آخر قرار دهید و همچنین بتوانید ذخیره کنید نمودار به شکل یک لیست مجاورت (یعنی با یک صف).
 
توضیحات رسمی الگوریتم
1) شماره رأسی را که جستجو از آن شروع می شود در صف اولیه خالی قرار دهید.
2) راس U را از ابتدای صف استخراج کرده و آن را به عنوان مورد استفاده در یک آرایه جداگانه علامت گذاری کنید.
3) در انتهای صف، تمام رئوس‌هایی را که می‌توانیم با استفاده از لبه راس U, به آنها برسیم و هنوز برچسب‌گذاری نشده‌اند، اضافه کنید.
4) اگر صف خالی باشد، تمام گره های گراف متصل شده اسکن شده اند، در غیر این صورت به مرحله 2 برگردید.
 
پیچیدگی
از آنجایی که الگوریتم در بدترین حالت از تمام گره های نمودار بازدید می کند، هنگام ذخیره نمودار به عنوان لیست های مجاورت، پیچیدگی زمانی الگوریتم O(|V| + |E|) است. ، که در آن V مجموعه ای از رئوس نمودار است و E مجموعه ای از یال ها است. به عبارت دیگر، الگوریتم در بدترین حالت برای عدد کار می کند. از یال ها + تعداد رئوس.

 

Training problem

BFS: شروع (C++)

BFS (جستجوی اول عرض) یک روش پیمایش گراف است که اغلب در الگوریتم های ساده و پیشرفته استفاده می شود. جستجوی Breadth-First با قدم گذاشتن در سطوح جداگانه نمودار، شروع از گره منبع و دور شدن تدریجی از آن کار می کند. این به وضوح در انیمیشن نشان داده شده است.
برای نوشتن یک BFS ساده، باید بتوانید با یک صف کار کنید، ساختار داده ای که به شما امکان می دهد از ابتدا  بردارید و آن را تا آخر قرار دهید و همچنین بتوانید یک نمودار را در فرم ذخیره کنید. از یک لیست مجاورت.
 
توضیحات رسمی الگوریتم
1) شماره رأسی را که جستجو از آن شروع می شود در صف اولیه خالی قرار دهید.
2) راس U را از ابتدای صف استخراج کنید و آن را به عنوان مورد استفاده در یک آرایه جداگانه علامت گذاری کنید.
3) در انتهای صف، تمام رئوسی را که می توانیم با استفاده از لبه از راس U به آنها برسیم و هنوز علامت گذاری نشده اند، اضافه کنیم.
4) اگر صف خالی باشد، تمام گره های گراف متصل شده اسکن شده اند، در غیر این صورت به مرحله 2 برگردید.
 
سختی کار
از آنجایی که در بدترین حالت، الگوریتم از تمام گره‌های گراف بازدید می‌کند، هنگام ذخیره نمودار در قالب لیست‌های مجاورت، پیچیدگی زمانی الگوریتم O(|V| + |E|) است، که در آن V مجموعه است. از رئوس نمودار، و E مجموعه ای از یال ها است.  ;
به عبارت دیگر، الگوریتم در بدترین حالت برای تعداد یال ها + تعداد رئوس کار می کند.

 

Training problem

BFS: Beginning (Python)

برای بازیابی کوتاه ترین مسیرها، آرایه ای از "اجداد" \(p[]\) ایجاد کنید. ، که در آن، برای هر رأس، تعداد رأسی که با آن به این راس برخورد کرده ایم، ذخیره می شود.

Training problem

مسیر