الگوریتم جستجوی سطح اول

در نظریهٔ گراف، جستجوی سطح-اول (به انگلیسی: Breadth-first Search، به‌اختصار: BFS) یکی از الگوریتم‌های پیمایش گراف است.

الگوریتم جستجوی سطح اول

Order in which the nodes get expanded Order in which the nodes are expanded
رده	الگوریتم جستجو
ساختمان داده	گراف (ساختار داده)
کارایی بدترین حالت	$O(|V|+|E|)=O(b^{d})$
پیچیدگی فضایی	$O(|V|)=O(b^{d})$

ترتیب پیمایش رئوس در جستجوی سطح اول

استراتژی جستجوی سطح اول برای پیمایش گراف، همان‌طور که از نامش پیداست «جستجوی سطح به سطح گراف» است.

عملکرد

الگوریتم از ریشه شروع می‌کند (در گراف‌ها یا درخت‌های بدون ریشه رأس دلخواهی به عنوان ریشه انتخاب می‌شود) و آن را در سطح یک قرار می‌دهد. سپس در هر مرحله همهٔ همسایه‌های رئوس آخرین سطح دیده شده را که تا به حال دیده نشده‌اند بازدید می‌کند و آنها را در سطح بعدی می‌گذارد. این فرایند زمانی متوقف می‌شود که همهٔ همسایه‌های رئوس آخرین سطح قبلاً دیده شده باشند. همچنین در مسائلی که حالات مختلف متناظر با رئوس یک گراف‌اند و حل مسئله مستلزم یافتن رأس هدف با خصوصیات مشخصی است که در عین حال در بین همهٔ رئوس هدف با آن خصوصیات به ریشه نزدیک‌ترین باشد، جستجوی سطح اول به صورت غیرخلاق عمل می‌کند. بدین ترتیب که الگوریتم هر دفعه همهٔ همسایه‌های یک رأس را بازدید کرده و سپس به سراغ رأس بعدی می‌رود و بنابراین گراف سطح به سطح پیمایش خواهد شد. این روند تا جایی ادامه می‌یابد که رأس هدف پیدا شود یا احتمالاً همهٔ گراف پیمایش شود. براساس آنچه گفته شد پیاده‌سازی هوشمندانهٔ الگوریتم آنقدر مؤثر نخواهد بود.

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

الگوریتم

پیاده‌سازی این الگوریتم مشابه پیاده‌سازی جستجوی عمق اول است با این تفاوت که به جای پشته از صف استفاده می‌شود. در این‌جا نیز مانند جستجوی عمق اول، preWORK را برای انعطاف بیشتر الگوریتم در نظر می‌گیریم که در زمان بررسی کردن هر رأس خارج شده از صف انجام می‌شود.

الگوریتم جستجوی اول سطح به صورت زیر است. آرایه Visited برای تعیین رئوس ملاقات شده بکار می‌رود. از یک صف برای نگهداشتن رئوس مجاور استفاده می‌شود. هر بار که راسی ملاقات می‌شود کلیه رئوس مجاور آن در صف اضافه می‌شود. پیمایش از راسی که از صف برداشته می‌شود ادامه پیدا می‌کند.

الگوریتم:

1. یکی به انتهای صف در گره جدید اضافه کن
2. در آن صف به جلو حرکت کرده و گره بعدی را امتحان کن الف-اگر پاسخ مورد نظر در آن گره پیدا شد، اتمام جستجو و نتیجه را برگردان ب-در غیر اینصورت زیرمجموعه‌های (فرزندان) مستقیم گره‌هایی را که جستجونشده بررسی کن
3. اگر صف دیگری وجود نداشت و همه گره‌ها بررسی شد، اتمام جستجو و «چیزی پیدا نشد» را برگردان
4. اگر صف به پایان نرسید برو مرحله ۲.

 BFS (int v){
 int w
 Queue q
 Visited[v]:=1
 CreateQueue(q)
 AddQueue(q, v)
 While (not EmptyQueue(q))
 DeleteQueue(q,v)
 For (all vertex w adjacent to v)
 If (not visited[w]) then
 AddQueue(q,w)
 Visited[w]:=1
 End if
 End For
 End while
 }

پیاده‌سازی

 1 Algorithm BFS(G,v)
 2 Input: G=(V,E), v(a vertex of G)
 3 Output: depends on the application
 4 begin
 5 mark v
 6 put v in the queue
 7 while the queue is not empty do
 8 remove first vertex w from the queue
 9 perform preWORK on w
10 for all edge (w,x) such that x is unmarked do
11 mark k
12 put x in the queue
13 end

پیاده‌سازی با متلب

در این الگوریتم اگر تعداد درایه‌های بردار خروجی برابر تعداد رئوس گراف ورودی باشد نشان می‌دهد که گراف همبند می‌باشد در غیر اینصورت گراف ناهمبند می‌باشد.

 1 function B=BFS(A)
 2  [r,c]=size(A);
 3 B=[1];
 4 z=[1];
 5 s=[1];
 6 while (~isempty(s))
 7 b=z(length(z));
 8 adj=find(A(b,:)==1);
 9 for t=1:length(adj)
10 if ~ismember(adj(t),B)
11 B=[B adj(t)];
12 end
13 end
14 s=setdiff(B,z);
15 if ~isempty(s)
16 z=[z s(1)];
17 end
18 end
19 end

پیچیدگی زمانی

هر رأس در صورتی وارد صف می‌شود که تا به حال دیده نشده باشد و بنابراین هر رأس قابل دسترسی از ریشه دقیقاً یک بار وارد صف خواهد شد. هر بار عمل ورود یک رأس به صف در $O(1)$ انجام می‌شود و لذا با فرض همبند بودن گراف اعمال مربوط به صف $O(|V|)$ از زمان صرف را صرف خواهند کرد. همچنین هر یال در گراف بدون جهت دقیقاً دو بار و هر یال در گراف جهت‌دار دقیقاً یک بار پیمایش خواهند شد. بدین ترتیب با فرض $O(1)$ بودن اعمال preWORK و همبندی گراف، پیچیدگی زمانی جستجوی سطح اول $O(|V|+|E|)$ خواهد بود.

کاربردها

• پیدا کردن مؤلفه‌های همبندی
• پیدا کردن کوتاهترین مسیرها از مبدأ واحد در گراف‌های بدون وزن
• آزمایش دوبخشی بودن یک گراف

پیوند به بیرون

• توضیح و مثال‌هایی از جستجوی سطح اول
• انیمیشن جستجوی سطح اول برای گراف‌های جهت‌دار
• توضیح و پیاده‌سازی جستجوی عمق اول و جستجوی سطح اول
• BFS Applet

منابع

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.
• Udi Manber. Introduction to Algorithms — A Creative Approach. MIT Press and Addison-Wesley, 1989. ISBN 0-201-12037-2.
• Donald E. Knuth. The Art Of Computer Programming Vol 1., Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4.
• Douglas B. West. Introduction to Graph Theory, Second Edition. Prentice Hall, 2001. ISBN 0-13-014400-2.