탐색 알고리즘 BFS

BFS(Breadth Frist Search)

너비우선탐색이라고도 불린다. 그래프를 깊게보다는 가까운 노드부터 넓게 탐색하는 알고리즘이다.
BFS의 탐색 순서는 다음과 같다.

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

BFS는 큐 자료구조를 이용해 데이터에 접근하며, 시간복잡도는 O(N)이 소요된다. BFS가 DFS보다 구현이 좀더 빠르게 동작한다.
주로 두 노드 사이의 최단경로, 혹은 임의의 경로를 찾고 싶을때 사용되는 알고리즘이다. DFS와 다르게 재귀적으로 동작하지 않는다.
다만 그래프 탐색시 어떤 노드를 방문했었는지를 반드시 체크해야한다. 그렇지 않으면 무한루프에 빠지게 된다.

BFS 구현 (java)

package DFS_BFS;

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

public class BFS {

    public static void main(String[] args) {
        // 그래프의 연결상태를 2차원 배열로 표현
        // 인덱스가 각각의 노드번호가 되고 0번 인덱스는 아무것도 없는 상태
        int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
        // 방문처리를 위한 boolean 배열 선언
        boolean[] visited = new boolean[9];

        System.out.println(bfs(1, graph, visited));
    }

    static String bfs(int start, int[][] graph, boolean[] visited) {
        // 탐색순서 출력용 스트링빌더
        StringBuilder sb = new StringBuilder();
        // 노드 탐색을 위한 큐
        Queue<Integer> q = new LinkedList<Integer>();

        // 시작노드 삽입 및 방문처리
        q.offer(start);
        visited[start] = true;

        // 큐에 데이터가 없을때까지 반복
        while(!q.isEmpty()) {
            // 큐에서 노드 꺼냄
            int nodeIndex = q.poll();
            sb.append(nodeIndex + " -> ");

            // 꺼낸 노드와 인접한 노드 순회
            for(int i = 0; i < graph[nodeIndex].length; i++) {
                int temp = graph[nodeIndex][i];
                // 방문처리 안된노드는 방문처리후 큐에 넣기
                if(!visited[temp]) {
                    visited[temp] = true;
                    q.offer(temp);
                }
            }
        }
        return sb.toString();
    }
}

참고자료
나동빈, 「이것이 코딩테스트다」
소스코드 : [Algorithm] BFS (Depth-first Search)를 Java로 구현해보자!