BFS 너비 우선 탐색 알고리즘

By Jimmyberg
algorithm bfs 알고리즘 너비우선탐색

너비 우선 탐색 알고리즘

너비 우선 탐색 알고리즘은 DFS와 동일하게 그래프 완전 탐색 기법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하여 탐색하는 알고리즘이다.

특징

  • FIFO 탐색
  • Queue 자료구조 활용
  • 시간 복잡도 : O(V + E)

구현 순서

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

  • 인접 리스트로 그래프 표현
node 1 : 2, 3
node 2 : 5, 6
node 3 : 4
node 4 : 6
node 5 : x
node 6 : x
  • Queue 자료구조에 시작점 더하기
ㅡㅡㅡㅡㅡㅡㅡ
1
ㅡㅡㅡㅡㅡㅡㅡ
  • 방문 배열 체크
check_arr : {T, F, F, F, F, F}

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

  • Queue에서 노드를 꺼내면서 인접 노드를 Queue에 삽입하고, 방문 배열을 체크하여 이미 방문한 인접 노드에 대해 Queue에 삽입한다. Queue 에서 꺼낸 노드는 탐색 순서에 기록한다.

  • 1를 꺼내면서, 인접 노드 node 2, 3 를 Queue 에 저장

ㅡㅡㅡㅡㅡㅡㅡ
3 2
ㅡㅡㅡㅡㅡㅡㅡ
  • 방문 배열 체크
check_arr : {T, T, T, F, F, F}

3. Queue에 값이 없을 때까지 반복하기

  • 1 ~ 2 번 순서를 Queue 자료구조에 값이 없어질 때까지 반복한다. 이미 다녀간 노드는 역시 삽입하지 않는다.
    • node 2 를 꺼내면, 인접 노드 node 5, 6를 Queue에 저장 및 방문 배열 체크
ㅡㅡㅡㅡㅡㅡㅡ
6 5 3
ㅡㅡㅡㅡㅡㅡㅡ
  • node 3 를 꺼내면, 인접 노드 node 4를 Queue에 저장 및 방문 배열 체크
ㅡㅡㅡㅡㅡㅡㅡ
4 6 5
ㅡㅡㅡㅡㅡㅡㅡ

BFS 실행 순서

node 1 : 2, 3
node 2 : 5, 6
node 3 : 4
node 4 : 6
node 5 : x
node 6 : x

실행 순서 : 1 -> 2 -> 3 -> 5 -> 6 -> 4

구현

/**
 * [Sample]
 * 5 5 3  // node 수, edge 수, 시작점
 * 5 4
 * 5 2
 * 1 2
 * 3 4
 * 3 1
 *
 * // 실행 순서
 * 3 1 4 2 5
 *
 * // 조건
 * 인접 노드가 여러 개일 경우, 번호가 작은 것부터 먼저 방문한다.
 */
public class BFS {
    static List<String> result;
    static List<List<Integer>> graph;
    static boolean[] visited;

    public static void main(String[] args) {
        System.out.println("============ START =============");
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int E = sc.nextInt();
        int start = sc.nextInt();

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        visited = new boolean[N + 1];

        for (int i = 0; i < E; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        for (List<Integer> child : graph) {
            child.sort(Comparator.comparingInt(o -> o));
        }

        bfs(start);

        System.out.println("bfs result : " + String.join(" ", result));
    }

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

        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(String.valueOf(node));
            for (int child : graph.get(node)) {
                if (!visited[child]) {
                    visited[child] = true;
                    queue.add(child);
                }
            }
        }
    }
}

출처