# 그래프 탐색이란

그래프 탐색에 대해서는 DFS 글에서도 확인할 수 있다.

# 너비 우선 탐색

너비 우선 탐색(Breadth-First Search)은 BFS라고 부른다. (이하 BFS라고 하겠다.)

루트 노드(혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법.

  • 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
  • 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
  • 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
    • Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
    • 깊이 우선 탐색의 경우 : 모든 친구 관계를 다 살펴봐야 할지도 모른다.
    • 너비 우선 탐색의 경우 : Ash와 가까운 관계부터 탐색.
  • BFS가 DFS보다 좀 더 복잡하다.

BFS의 특징

  • 직관적이지 않은 면이 있다.
    • BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
  • BFS는 재귀적으로 동작하지 않는다.
  • 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다.
    • 이를 검사하지 않을 경우 무한 루프에 빠질 위험이 있다.
  • BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
    • 즉, 선입선출 원칙으로 탐색
    • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

BFS의 탐색 과정

  1. a 노드(시작 노드)를 방문한다.(방문한 노드 체크)
    • 큐에 방문된 노드를 삽입한다.(enqueue)
    • 초기 상태의 큐에는 시작 노드만 저장
      • 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
  2. 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
    • 큐에서 꺼낸 노드를 방문한다.
    • 큐에서 꺼낸 노드와 인접한 노드들을 모두 방문한다.
      • 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다.(dequeue)
    • 큐에 방문된 노드를 삽입한다.(enqueue)
  3. 큐가 소진될 때까지 계속한다.

BFS의 구현

  • 구현 방법
    • 자료 구조인 큐(Queue)를 사용.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.io.*;
import java.util.*;

/**
 * created by victory_woo on 02/04/2019
 * DFS와 BFS 복습
 */
public class BOJ1260_RE {
    private static final String SPACE = " ";
    private static ArrayList<Integer>[] a;
    private static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(SPACE);
        int n = convert(input[0]); // 정점의 개수
        int m = convert(input[1]); // 간선의 개수
        int start = convert(input[2]); // 시작할 정점 번호

        // 배열 초기화.
        a = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            a[i] = new ArrayList<>();
        }

        for (int j = 0; j < m; j++) {
            String[] inputs = br.readLine().split(SPACE);
            int u = convert(inputs[0]);
            int v = convert(inputs[1]);

            // 양방향 그래프일 경우 양쪽 다 추가해준다.
            a[u].add(v);
            a[v].add(u);
        }

        // 방문할 정점이 여러 개인 경우 정점 번호가 가장 작은 것부터 탐색하기 위해서 정렬한다.
        for (int i = 1; i <= n; i++) {
            Collections.sort(a[i]);
        }

        visit = new boolean[n + 1];
        bfs(start);
        System.out.println();
    }

    private static int convert(String command) {
        return Integer.parseInt(command);
    }

    private static void bfs(int start) {
        LinkedList<Integer> queue = new LinkedList<>();

        visit[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) {
            int x = queue.remove(); // 큐에서 정점을 뺀다.

            System.out.print(x + SPACE);

            for (int y : a[x]) {
                // 방문한 적이 있는지 체크한다.
                if (!visit[y]) {
                    // 해당 정점을 방문한 적이 없다면 방문했다고 true 로 체크한다.
                    // 그리고 해당 정점을 큐에 넣는다.
                    visit[y] = true;
                    queue.add(y);
                }
            }
        }
    }
}
// 입력
5 5 3
5 4
5 2
1 2
3 4
3 1
// 출력 결과
3 1 4 2 5

BFS의 시간 복잡도

  • N : 정점의 개수, E : 간선의 개수
  • 인접 리스트로 표현된 그래프 : O(N+E)
  • 인접 행렬로 표현된 그래프 : O(N^2)
  • DFS와 마찬가지로 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

참고