الگوریتم جستجوی پهنا نخست

Question

سلام؛ اگر ممکنه در مورد الگوریتم جستجوی پهنا نخست یا BFS در گراف یه توضیح بدید.

Answer 1

جستجوی اول سطح

در جستجوی اول سطح پيمايش از يک راس آغاز می شود. آن راس و کليه رئوس مجاورش ملاقات می شود سپس پيمايش از راس مجاور ادامه پيدا می کند.

الگوريتم جستجوی اول سطح به صورت زير است. آرايه 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(n²) و اگر از لیست مجاورتی استفاده شود O(m)‌ است.

مثال. مراحل اجرای BFS(v1) برای يک گراف در شکل زير نشان داده شده است.