BFS (너비우선탐색)

🔖 알고리즘 예시 (Java)

---

BFS (Breadth-First Search)

그래프 탐색 알고리즘 중 너비 우선 탐색 알고리즘 입니다.

 

 

BFS 동작 과정

1. 시작 정점을 방문하고 Queue에 넣습니다.

2. Queue에서 정점을 하나 꺼내고 인접한 정점들을 방문하고, 방문한 정점은 Queue에 넣습니다.

3. Queue가 빌 때까지 위 과정을 반복합니다.

 

 

BFS 특징

• 최단 경로를 찾을 때 유용합니다.
  시작 정점에서 거리가 가까운 정점부터 방문하기 때문에 먼저 도달하는 정점이 더 가까운 정점입니다.
• Queue 자료구조를 사용합니다.
• 시간 복잡도 : O(V + E) 
  (모든 정점을 방문하기 때문)

 

 

BFS 주요 활용

• 네트워크 최단 경로 탐색
• 그래프의 연결성 확인
• 트리의 레벨 순회

 

 

 

[ psudo code ]

BFS(v) {
     que.push(v);                ▶ 우선, 시작점을 큐에 넣기
     visited[v] = true;

     while( !que.empty() ) {
          u = que.front();
          que.pop();
          for( i = 0 to n ) :
               if( visited[i] == false AND table[u][i] = 1 ) :
                     que.push(i);
                     visited[i] = true;
     }
}