الگوریتم جستجوی سطح اول
در نظریهٔ گراف، جستجوی سطح-اول (به انگلیسی: Breadth-first Search، بهاختصار: BFS) یکی از الگوریتمهای پیمایش گراف است.
رده | الگوریتم جستجو |
---|---|
ساختمان داده | گراف (ساختار داده) |
کارایی بدترین حالت | |
پیچیدگی فضایی |
استراتژی جستجوی سطح اول برای پیمایش گراف، همانطور که از نامش پیداست «جستجوی سطح به سطح گراف» است.
عملکرد
الگوریتم از ریشه شروع میکند (در گرافها یا درختهای بدون ریشه رأس دلخواهی به عنوان ریشه انتخاب میشود) و آن را در سطح یک قرار میدهد. سپس در هر مرحله همهٔ همسایههای رئوس آخرین سطح دیده شده را که تا به حال دیده نشدهاند بازدید میکند و آنها را در سطح بعدی میگذارد. این فرایند زمانی متوقف میشود که همهٔ همسایههای رئوس آخرین سطح قبلاً دیده شده باشند. همچنین در مسائلی که حالات مختلف متناظر با رئوس یک گرافاند و حل مسئله مستلزم یافتن رأس هدف با خصوصیات مشخصی است که در عین حال در بین همهٔ رئوس هدف با آن خصوصیات به ریشه نزدیکترین باشد، جستجوی سطح اول به صورت غیرخلاق عمل میکند. بدین ترتیب که الگوریتم هر دفعه همهٔ همسایههای یک رأس را بازدید کرده و سپس به سراغ رأس بعدی میرود و بنابراین گراف سطح به سطح پیمایش خواهد شد. این روند تا جایی ادامه مییابد که رأس هدف پیدا شود یا احتمالاً همهٔ گراف پیمایش شود. براساس آنچه گفته شد پیادهسازی هوشمندانهٔ الگوریتم آنقدر مؤثر نخواهد بود.
از دیدگاه عملی، برای پیادهسازی این الگوریتم از صف استفاده میشود. بدین ترتیب که در ابتدا ریشه در صف قرار میگیرد. سپس هر دفعه عنصر ابتدای صف بیرون کشیده شده، همسایگانش بررسی شده و هر همسایهای که تا به حال دیده نشده باشد به انتهای صف اضافه میشود. جزئیات پیادهسازی در ادامه خواهد آمد.
الگوریتم
پیادهسازی این الگوریتم مشابه پیادهسازی جستجوی عمق اول است با این تفاوت که به جای پشته از صف استفاده میشود. در اینجا نیز مانند جستجوی عمق اول، preWORK را برای انعطاف بیشتر الگوریتم در نظر میگیریم که در زمان بررسی کردن هر رأس خارج شده از صف انجام میشود.
الگوریتم جستجوی اول سطح به صورت زیر است. آرایه Visited برای تعیین رئوس ملاقات شده بکار میرود. از یک صف برای نگهداشتن رئوس مجاور استفاده میشود. هر بار که راسی ملاقات میشود کلیه رئوس مجاور آن در صف اضافه میشود. پیمایش از راسی که از صف برداشته میشود ادامه پیدا میکند.
الگوریتم:
- یکی به انتهای صف در گره جدید اضافه کن
- در آن صف به جلو حرکت کرده و گره بعدی را امتحان کن الف-اگر پاسخ مورد نظر در آن گره پیدا شد، اتمام جستجو و نتیجه را برگردان ب-در غیر اینصورت زیرمجموعههای (فرزندان) مستقیم گرههایی را که جستجونشده بررسی کن
- اگر صف دیگری وجود نداشت و همه گرهها بررسی شد، اتمام جستجو و «چیزی پیدا نشد» را برگردان
- اگر صف به پایان نرسید برو مرحله ۲.
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
پیچیدگی زمانی
هر رأس در صورتی وارد صف میشود که تا به حال دیده نشده باشد و بنابراین هر رأس قابل دسترسی از ریشه دقیقاً یک بار وارد صف خواهد شد. هر بار عمل ورود یک رأس به صف در
کاربردها
- پیدا کردن مؤلفههای همبندی
- پیدا کردن کوتاهترین مسیرها از مبدأ واحد در گرافهای بدون وزن
- آزمایش دوبخشی بودن یک گراف
پیوند به بیرون
منابع
- 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.