الگوریتم جستجوی اول سطح (BFS)
الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth First Search – BFS) از جمله الگوریتمهای مشهور پیمایش و جستجوی گراف است که در حل مسائل الگوریتمی و هوش مصنوعی کاربرد دارد. این الگوریتم برای پیمایش و جستجوی گراف از یک صف برای نگهداری ترتیب جستجو استفاده میکند.
الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع شده و تا خالی نشدن این صف مراحل زیر را تکرار میکند:
- عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف کن.
- گره جاری را پردازش کن.
- گرههای مجاور گره جاری که پردازش نشده و در صف پردازش نیز قرار ندارند به این صف اضافه کن.
در ادامه قصد داریم برنامهای بنویسیم که گراف روبرو را به روش BFS پیمایش کند و ترتیب رؤیت گرهها را در خروجی چاپ نماید (فرزندان یک گره به ترتیب حروف الفبا رؤیت شوند.)
فرض میکنیم که جستجو از گره C که ما شماره آنرا ۲ در نظر گرفتهایم شروع شده است ولی برنامه این قابلیت را دارد که با تغییر این عدد، بتوانیم از هر گره دلخواه دیگری نیز شروع کنیم.