너비 우선 탐색(BFS: Breadth First Search)

너비 우선 탐색(BFS)란?

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 큐를 이용해서 지금 위치에서 갈 수 있는 곳을 모두 큐에 넣는 방식
  • 큐에 넣을 때 방문했다고 체크
• 모든 가중치가 1일때 최단 거리를 구하는 알고리즘

너비 우선 탐색 알고리즘

breadth_first_search(v)

   v를 방문되었따고 표시;
   큐 Q에 정점 v를 삽입;
    while (not is_empty(Q)) do
        Q에서 정점 w를 삭제;
        for all u ∈ (w에 인접한 정점) do
            if (u가 아직 방문되지 않았으면)
                then u를 큐에 삽입;
                         u를 방문되었다고 표시;