자바 java BFS Breadth First Search 너비우선탐색

BFS 너비 우선 탐색 Breadth First Search

최단거리 구하는 문제를 풀 때 유용합니다.

 

• BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색
• BFS는 같은 레벨에 있는 노드들을 먼저 탐색하고 그다음 레벨 노드를 탐색함
• 특정 노드에서 다른 노드까지 최단값 또는 임의의 경로를 찾을 때 사용
• 스택이 아닌 큐(Queeu) 구조를 활용
• FIFO 원칙으로 탐색

BFS 수행 과정

1. 현재 레벨에 있는 root Node를 Q.offer에 넣어서 Q.size, 큐의 길이 계산
2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 방문
3. 인접한 노드가 없으면 큐의 앞에서 노드를 꺼냄 (dequeue)
4. 큐에 방문된 노드를 삽입 한다
5. 큐에 가 공백 상태가 될 때까지 계속 한다 Q.isEmpty() = true 일 때 종료

 

활용 예제

 

Q. 그림과 같은 그래프에 대하여 정점의 개수 N, 연결선의 개수 M이 주어지고 그래프에 대한 연결 정보가 주어질 때, 시작정점 1에서 BFS 방문경로를 출력하시오.

 

그래프 정보

문제 풀이

 

시작 정점 1 bfs() 함수 실행, Queue를 이용하여 

다음 정점과 연결되어 있고 (map[x][i] ==1),

아직 방문하지 않은 정점 (visited[i] == false)

큐에 해당 정점을 넣어주고, 더 이상 방문할 저점이 존재하지 않으면 종료한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;

public class bfsprac {
    static int[][] map;
    static boolean[] visited;
    static StringTokenizer st;
    static int N, M, start, end;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 정점의 개수
        M = Integer.parseInt(br.readLine()); // 간선의 개수

        map = new int[N+1][N+1];
        visited = new boolean[N+1]; // 방문 여부를 검사할 배열

        for (int m =0; m < M; m++){//그래프 정보 입력받기
            st = new StringTokenizer(br.readLine(), " ");
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());
            map[start][end] =1;
            map[end][start] =1;
        }
        System.out.print("그래프 BFS 방문 순서 :");
        bfs(1);
    }

    static void bfs(int point) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(point);
        visited[point] =true;

        while (!queue.isEmpty()) {
            int x = queue.poll();
            System.out.print(x+" ");

            for (int i =1; i<=N; i++){
                if (map[x][i] ==1 && visited[i]==false){ //다음 정점과 연결되어 있고 아직 방문하지 않았다면
                    queue.offer(i);
                    visited[i]=true;
                }
            }
        }
    }

}

Console

7
8
1 2
1 3
2 4
2 5
3 7
4 6
5 6
6 7
그래프 BFS 방문 순서 :1 2 3 4 5 7 6