BFS - 자바(JAVA)

BFS는 너비우선 탐색이다.

그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. 

 

기능	특징	시간복잡도
그래프 완전 탐색	FIFO(선입선출) Queue 자료구조 이용	O(V + E)

 

● 너비 우선 탐색은 선입선출 방식으로 탐색하므로 Queue를 이용해 구현한다.

● 시작 노드를 기준으로 가까운 노드를 먼저 방문하기 때문에 도착하는 경로가 여러 개일 때 최단경로를 보장한다.

 

핵심이론

1. BFS를 시작할 노드 정한 후 사용할 자료구조 초기화

- 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요하다.

- 자료구조는 Queue를 사용한다.

 

2.  Queue에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 Queue에 삽입한다.

- Queue에서 노드를 꺼내면서 인접 노드를 다시 Queue에 삽입한다. 

- 이때 방문 배열을 체크해서 이미 방문한 노드는 다시 Queue에 삽입하지 않는다.

- 탐색 순서가 필요하면 Queue에서 노드를 꺼내면서 순서를 기록한다. 

 

3. Queue에 남은 노드가 없을 때까지 반복한다.

 

 

코드

private static void BFS(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visted[node] = ture;
        while(!queue.isEmpty()) {
            int now_node = queue.poll();
            System.out.println(now_node + "");
            for(int i : A[now_node]){
                if(!visted[i]) {
                    queue.add(i);
                    visted[i] = ture;
                }
            }
        }
    }