جستجوی اول سطح
در جستجوی اول سطح پيمايش از يک راس آغاز می شود. آن راس و کليه رئوس مجاورش ملاقات می شود سپس پيمايش از راس مجاور ادامه پيدا می کند.
الگوريتم جستجوی اول سطح به صورت زير است. آرايه 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
}
برای گراف G با n راس و m يال ، مرتبه اجرائی الگوريتم وقتی گراف توسط ماتریس مجاورتی نمايش داده شده باشد O(n2) و اگر از لیست مجاورتی استفاده شود O(m) است.
مثال. مراحل اجرای BFS(v1) برای يک گراف در شکل زير نشان داده شده است.