BFS ( Breadth-First Search )

BFS는 그래프 탐색 알고리즘 중 하나로,
루트 노드에서 시작해서 인접한 노드를 모두 우선 탐색한 후에
그 인접한 노드들의 인접한 노드를 다시금 차례로 탐색해나가는 방식으로 동작한다.

즉, 레벨 순서대로 탐색하는 알고리즘이다.

BFS는 Queue 자료구조 를 사용한다

Queue는 먼저 집어넣은 데이터가 먼저 나오는 선입선출(FIFO)의 구조를 가지므로,
BFS에서는 먼저 방문한 노드를 큐에 삽입하고 해당 노드와 인접한 노드들을
모두 큐에 삽입한 후에 큐에서 노드를 꺼내서 방문을 진행한다.

BFS를 이용해 탐색하는 방법은 다음과 같다.

• 1. 정점을 N, 간선을 E로 변수 선언
• 2. 2차원 배열 Graph[][] 를 선언하고 각 노드들의 관계를 저장
  • 예를 들어, 방향성이 없는 간선으로 1번 정점과 2번 정점이 연결되어 있다면
    Graph[1][2] = Graph[2][1] = 1;
    위와 같이 저장해서 각 정점이 1이라면 이어져 있음을 표시
• 3. 각 노드의 방문 여부를 확인하는 Visited[] 배열을 선언
• 4. BFS 구현을 위해 따로 메서드로 선언, 매개변수로 시작 Node를 넘김
• 5. Queue를 선언하고 시작 노드를 q에 삽입
• 6. 시작노드 방문을 표시하기 위해 Visited[node] = true
• 7. Queue가 모두 빌 때 까지 반복,
• 8. Queue에서 노드를 하나 꺼낸 뒤, 그 노드와 연결된 모든 노드를 탐색
• 9. 탐색된 노드가 방문하지 않았고 ( !Visited[next] )
     현재 노드와 연결된 노드라면 ( Graph[curr][next] != 0 ) Queue에 삽입하면서 방문체크

-  Java Code
/* BFS : Breadth First Search */

    static final int MAX_N = 10;
    static int E, N;
    static int Graph[][] = new int[MAX_N][MAX_N];

    static void bfs(int node) {
        boolean visited[] = new boolean[MAX_N];

        // 자바 자료형중 하나인 Queue. Queue 는 보통 LinkedList 를 사용해야한다.
        Queue<Integer> myQueue = new LinkedList<>();

        // 방문했다는 의미의 true
        visited[node] = true;

        // 큐에 현재 node 삽입
        myQueue.add(node);

        // 큐가 빌 때 까지 무한반복
        while(!myQueue.isEmpty()) {

            // 큐에서 값을 꺼내 임시변수에 저장
            int curr = myQueue.remove();

            System.out.print(curr + " ");

            for (int next = 0; next < N; ++next) {
                if (!visited[next] && Graph[curr][next] != 0) {
                    visited[next] = true;
                    myQueue.add(next);
                }
            }

        }

    }

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        E = scan.nextInt();
        N = scan.nextInt();

        for (int i = 0; i < E; i++) {
            int u = scan.nextInt();
            int v = scan.nextInt();
            Graph[u][v] = Graph[v][u] = 1;
        }

        bfs(0);

    }