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

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

Procedure BFS(v) 
Visit(v) 
AddQueue(v) 
While Queue is not empty do 
DeleteQueue(v) 
For each w adjacent to v do 
If not visited w then 
Visit(w) 
AddQueue(w) 
Endif 
Repeat 
Repeat 
end
در الگوریتم بالا در بدترین وضعیت (گراف همبند باشد) هر یال حداکثر دو بار پیموده می‌شود و هر راس نیز یکبار ملاقات می‌شود و لذا مرتبه زمانی الگوریتم(o(n +eاست.
توسط الگوریتم‌های DFS و BFS میتوانیک گراف همبند را نیز پیمایش کرد.به این صورت که هر بار از یک گره ملاقات نشده شروع کرده و آن را DFS یا BFS می کنیم و لذا می‌توان به الگوریتم‌هایی مبتنی بر پیمایش عمقی یا ردیفی رسید.

منابع 

 ebook.veyq.ir 

 www.irandisheh.com 

 www.nooreaseman.com 

 www.iran-stu.com 

 com-eng.ir

الگوریتم‌های جستجو