BFS

BFS(Breadth First Search)

: 너비 우선 탐색
: 가까운 노드부터 탐색하는 알고리즘
: 큐 자료구조를 이용

인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어,
가까운 노드부터 탐색을 진행하게 된다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

예시) 더보기 클릭

다음과 같은 그래프를 살펴보자.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

탐색을 수행함에 있어 O(N)의 시간이 소요된다.
코딩 테스트에서는 보통 DFS보다는 BFS 구현이 조금 더 빠르게 동작한다.

 

 

예제 코드 - java)

package exam05_dfs_bfs;

import java.util.LinkedList;
import java.util.Queue;

public class BFS_Exam {
    public static void bfs(int[][] graph, int start, boolean[] visited){
        // 큐로 구현
        Queue<Integer> q = new LinkedList();
        q.add(start);
        // 현재 노드를 방문 처리
        visited[start] = true;

        // 큐가 빌 때까지 반복
        while(!q.isEmpty()){
            // 큐에서 하나의 원소를 뽑아 출력
            int v = q.poll();
            System.out.print(v +" ");
            // 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
            for(int i : graph[v]){
                if(!visited[i]){
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[][] graph = {
                {},
                {2, 3, 8},
                {1, 7},
                {1, 4, 5},
                {3, 5},
                {3, 4},
                {7},
                {2, 6, 8},
                {1, 7}
        };
        boolean[] visited = new boolean[9];

        bfs(graph, 1, visited);

    }
}