[Java] BFS : 너비 우선 탐색

너비우선탐색

개요

너비 우선 탐색은 최초 위치에서 가까운 노드들을 우선적으로 탐색하는 방법이다.

여기서 가깝다는 의미는 가중치가 적은 것이 아니라, 몇 번 만에 도달할 수 있는가를 의미한다.

알고리즘에 사용할 그래프

시간 복잡도

인접리스트로 구현된 경우에는 각 노드마다 모든 간선을 확인해야 하므로, O(|V|+|E|)
입접 행렬로 구현된 경우에는 각 노드마다 다른 노드로 연결되어 있는지 확인해야 하므로, O(|V|^2)

동작

처음엔 1번 노드를 방문한다.

1번 노드와 직접 연결된 2, 6 노드를 큐에 넣는다.

2번 노드를 방문한다.

2번 노드와 직접 연결된 3, 4 노드를 큐에 넣는다.

6번 노드를 방문한다.

4번은 이미 큐에 들어가 있으므로, 3번 노드를 방문한다.

4번 노드를 방문한다.

4번 노드와 직업 연결된 5, 7번 노드를 큐에 넣는다.

5번 노드를 방문한다.

7번은 이미 큐에 있으니 제외하고, 5번과 직업 연결된 노드 8을 큐에 넣는다.

7번 노드를 방문한다.

8번 노드를 방문한다. 큐에 남은 노드가 없으므로 종료한다.

코드

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

public class 너비_우선_탐색 {
    // 그래프의 인접리스트
    static Vector<Vector<Integer>> adj;

    static Vector<Integer> bfs(int start) {
        Vector<Boolean> discovered = new Vector<>();
        for (int i = 0; i < adj.size(); i++) {
            discovered.add(false);
        }

        // 방문할 정점 목록을 유지하는 큐
        Queue<Integer> q = new LinkedList<>();

        // 방문 순서 기록
        Vector<Integer> order = new Vector<>();

        // 맨 처음 위치 방문
        discovered.set(start, true);

        q.add(start);

        while (!q.isEmpty()) {
            int here = q.poll();
            // here를 방문
            order.add(here);

            for (int i = 0; i < adj.get(here).size(); i++) {
                int there = adj.get(here).get(i);
                // 방문하지 않았다면 방문할 목록에 추가
                if (!discovered.get(there)) {
                    q.add(there);
                    discovered.set(there, true);
                }
            }
        }

        return order;
    }

    public static void main(String[] args) {
        adj = new Vector<>();

        for (int i = 0; i < 8; i++) {
            adj.add(new Vector<>());
        }

        adj.get(0).add(1);
        adj.get(0).add(5);

        adj.get(1).add(0);
        adj.get(1).add(2);
        adj.get(1).add(3);

        adj.get(2).add(1);

        adj.get(3).add(4);
        adj.get(3).add(5);
        adj.get(3).add(6);

        adj.get(4).add(3);
        adj.get(4).add(6);
        adj.get(4).add(7);

        adj.get(5).add(0);
        adj.get(5).add(3);

        adj.get(6).add(3);
        adj.get(6).add(4);

        adj.get(7).add(4);

        Vector<Integer> result = bfs(0);

        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i) + " 방문");
        }
    }
}

출력

1 방문
2 방문
6 방문
3 방문
4 방문
5 방문
7 방문
8 방문