جستجو و پیمایش ردیفی اول سطح
 | این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
اگر در الگوریتم پیمایش عمقی به جای پشته یک صف در نظر بگیریم به الگوریتم جدیدی خواهیم رسیدکه 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