الگوریتم جستجوی اول سطح (BFS) - الگوریتمستان
الگوریتمستان
1214.005.00
  »  

       

معرفی الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C

الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth First Search - BFS) از جمله الگوریتم‌های مشهور پیمایش و جستجوی گراف است که در حل مسائل الگوریتمی و هوش مصنوعی کاربرد دارد. این الگوریتم برای پیمایش و جستجوی گراف از یک صف برای نگهداری ترتیب جستجو استفاده می‌کند.

    الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع شده و تا خالی نشدن این صف مراحل زیر را تکرار می‌شود:

    1- عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف کن.

    2- گره جاری را پردازش کن.

    3- گره‌های مجاور گره جاری که پردازش نشده و در صف پردازش نیز قرار ندارند به این صف اضافه کن.

    منظور از پردازش، هر عملی روی گره است که پیمایش یا جستجو به آن نیت صورت گرفته است.

    به عنوان مثال در گراف زیر:

        

جستجوی اول سطح - BFS

      

    ترتیب پیمایش گره‌ها با شروع از گره شماره‌ی 1 به این ترتیب خواهد بود:

      

1, 2, 3, 4, 8, 7, 5, 6

جستجوی اول سطح - BFS

      

    دلیل نام‌گذاری این روش با عبارت "اول سطح" در پیمایش یک درخت از ریشه مشخص می‌شود که گره‌ها به صورت سطح به سطح پیمایش می‌شوند و اولویت پیمایش با سطح گره است.

    نکته: ممکن است هدف از اجرای الگوریتم BFS یافتن یک گره با مشخصات خاص در گراف باشد. در این حالت گره مذکور (در صورت وجود) ممکن است زودتر از خالی شدن صف پردازش یافت شده و نیازی به ادامه‌ی الگوریتم و پیمایش سایر گره‌ها نباشد.

      

پیاده‌سازی الگوریتم جستجوی اول سطح

  [بازگشت به فهرست]

تابع bfs یک پیاده‌سازی ساده از الگوریتم BFS به زبان برنامه‌نویسی ++C است که با دریافت مشخصات گراف و شماره‌ی اندیس گره مبدأ، گراف را پیمایش کرده و شماره‌ی عدد هر گره را به عنوان پردازش آن چاپ می‌کند:

      

void bfs(int graph[MAX][MAX], int numberOfNodes, int sourceNode){
  queue<int> processQueue;
  bool visited[MAX] = { false };
  processQueue.push(sourceNode);
  visited[sourceNode] = true;
  while(!processQueue.empty()){
    int currentNode = processQueue.front();
    processQueue.pop();
    cout << currentNode + 1 << "\t" << endl;
10     for(int i = 0 ; i < numberOfNodes ; i++)
11       if(graph[currentNode][i] < INT_MAX && !visited[i]){
12         processQueue.push(i);
13         visited[i] = true;
14       }
15   }
16 }

  

    این تابع با استفاده از آرایه‌ی visited قرار گرفتن گره در صف و پردازش آن را مشخص می‌کند. حلقه‌ی for بررسی یال‌های مجاور گره جاری برای اضافه شدن به صف را بر عهده داشته و حلقه‌ی while تا زمان خالی شدن صف تکرار می‌شود.

      

مرتبه‌ی زمانی الگوریتم جستجوی اول سطح

  [بازگشت به فهرست]

در گراف (G = (V, E مرتبه‌ی زمانی الگوریتم جستجوی اول سطح (|O(|V| + |E است؛ چرا که این الگوریتم در بزرگترین حالت تمامی گره‌ها را پیمایش کرده و نیاز به بررسی تمامی یال‌ها دارد. این مرتبه‌ی اجرایی در یک گراف همبند به صورت (|O(|E بوده (چرا؟) و در حالت کلی متناسب با تعداد یال‌ها حداکثر از مرتبه‌ی (O(n2 است.

      

کاربردهای الگوریتم جستجوی اول سطح

  [بازگشت به فهرست]

یک کاربرد مهم الگوریتم BFS تشخیص همبندی گراف یا مؤلفه‌های همبندی آن است. اگر نتیجه‌ی پیمایش گراف با این الگوریتم شامل تمامی گره‌های آن باشد، به معنی همبند بودن گراف است؛ اما اگر اینگونه نباشد، متناسب با جهت‌دار بودن یا نبودن گراف نتیجه‌ی مختلفی برداشت می‌شود. این حالت در گراف بدون جهت به معنی ناهمبند بودن گراف بوده و در گراف جهت‌دار صرفا می‌توان مطمئن شد که گراف قویا همبند نیست. اگر در پیمایش به وسیله‌ی BFS از یک گره مشخص تمامی گره‌ها بازدید نشوند، می‌توان با گره دیگری خارج از گره‌های بازدید شده‌ی قبلی الگوریتم را مجددا تکرار کرده و به یک مؤلفه‌ی همبندی دیگر رسید. در گراف جهت‌دار ممکن است گره‌های جدید با گره‌های بازدید شده‌ی قبلی اشتراک داشته باشند که نشان از وجود مسیرهایی از بخش دوم به بخش اول دارد؛ اما به طور حتم هیچ‌کدام از این مسیرها دو طرفه نیستند.

    کاربرد دیگری از الگوریتم BFS تولید یک درخت پوشا برای گراف است. اگر هر گره پیمایش شده در الگوریتم BFS را به گره‌هایی که توسط آن وارد صف می‌شوند متصل کنیم، یک درخت پوشا از مجموعه‌ی آن گره‌ها تولید می‌شود. اگر گراف همبند باشد، درخت حاصل درخت پوشای کل گراف خواهد بود. تکرار این کار روی مؤلفه‌های همبندی یک گراف ناهمبند نیز یک جنگل از درخت‌های پوشای محلی تولید می‌کند.

    تذکر: درخت پوشای تولید شده با الگوریتم BFS برای یک گراف وزن‌دار لزوما درخت پوشای کمینه نیست.

    کاربرد دیگر الگوریتم BFS برای پیمایش صفحات مارپیچ (Maze) است که در بازی‌ها و همینطور مباحث رباتیک برای تشخیص مسیر بسیار کاربرد دارد. یک صفحه‌ی مشبک را در نظر بگیرید که دو ربات (موش) و چند خانه‌ی هدف (پنیر) در یک محوطه‌ی محصور توسط موانع قرار دارند:

      

جستجوی اول سطح - BFS - مارپیچ (Maze)

      

    هدف برنامه‌‌نویسی ربات‌های موش برای جمع کردن پنیرهای موجود است. ربات تنها مجاز به حرکت از هر خانه به چهار خانه‌ی مجاور خود در صورت نبود مانع است. چنین ساختاری با گراف قابل شبیه‌سازی است؛ به این ترتیب که هر خانه یک گره در نظر گرفته شده و خانه‌های مجاور در صفحه با یال به هم متصل می‌شوند. این مثال ساده نشان از گراف بدون جهتی دارد که هزینه‌ی حرکت از هر گره به گره‌های مجاور خود ثابت و برای هر دو گره مجاور یکسان است. بنابراین می‌توان آن را به صورت گراف بدون وزن در نظر گرفت. درخت پوشای تولید شده با الگوریتم BFS از محل شروع حرکت ربات، کوتاهترین مسیر حرکت به هر هدف را مشخص کرده و امکان تشخیص نزدیکترین هدف را فراهم می‌کند.

      

جستجوی اول سطح - BFS - مارپیچ (Maze)

      

    تذکر: در الگوریتم جستجوی اول سطح جهت یال‌ها مهم بوده، اما وزن یال‌ها هیچ نقشی ندارند. ممکن است متناسب با نیاز، معیار وزن به طریقی در الگوریتم وارد شود؛ به عنوان مثال گره‌ها به ترتیب وزنشان وارد صف شده و پیمایش شوند؛ اما چنین قانونی در ذات این الگوریتم وجود ندارد. استفاده از این الگوریتم در maze به خاطر بدون وزن بودن گراف معادل صفحه است. به عبارت دیگر، هزینه‌ی حرکت از یک گره به گره دیگر برابر تعداد یال‌های مسیر است. اگر یال‌ها وزن‌دار باشند، مسیر مشخص شده توسط این الگوریتم لزوما کم‌هزینه‌ترین مسیر نیست. الگوریتم دایکسترا نمونه‌ای از راهکاری مبتنی بر پیمایش BFS است که کوتاهترین مسیر در گراف‌های وزن‌دار با وزن‌های متنوع را مشخص می‌کند.


این نوشته آخرین بار در تاریخ سه‌شنبه، ۵ مرداد ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        بررسی مسئله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان
        بررسی مسئله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge
        بررسی مسئله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان
        معرفی الگوریتم جستجوی اول عمق (DFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
        آشنایی با الگوریتم فلوید-وارشال برای یافتن کوتاهترین مسیرهای گراف با قطعه کد نمونه به زبان برنامه‌نویسی ++C
        آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C
        بررسی مسئله‌ی آسانسورها (Elevators)، از سوالات مسابقات برنامه‌نویسی ACM
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

 


» سبحان

پنجشنبه، ۲۱ اسفند ماه ۱۳۹۳، ساعت ۱۷:۰۹
خیلی ممنون121212

» محمد

چهارشنبه، ۲۷ مرداد ماه ۱۳۹۵، ساعت ۱۵:۱۲
سلام
میخواستم ببینم چه موقع dfs از bfsسریعتر است؟؟


یکشنبه، ۳۱ مرداد ماه ۱۳۹۵، ساعت ۰۷:۲۰
مسعود:
سلام
منظورتون از سرعت چی هست؟ اگه زمان پیمایش کل گراف منظورتونه، به پیاده‌سازی الگوریتم و همینطور پیاده‌سازی صف یا پشته بستگی داره. در حالت ایده‌آل هم تفاوت چندانی ندارن.
اما اگه منظورتون زمان دسترسی به گره مطلوب باشه، بسته به مسأله ممکنه استفاده از یکی از این دو الگوریتم بهتر باشه.