[그래프의 탐색] DFS(깊이 우선 탐색), BFS(너비 우선탐색) 알아보기 : Programming Story

1. 그래프 탐색의 필요성

굉장히 인기있는 그래프의 탐색이라는 주제,
우리는 왜 공부해야 하는 것일까?
목적은 임의의 정점에서 시작하여 연결되어 있는 모든 정점을 1번씩 방문하기 위해서이다.

2. 그래프 탐색의 종류

그래프의 탐색에는 크게 두 가지 방법이 있다.
DFS (Depth First Search: 깊이 우선 탐색) 과 BFS(Breadth First Search: 너비 우선 탐색) 이다.

각각의 방법을 하나씩 알아보자.

1) DFS (Depth First Search) : 깊이 우선 탐색

깊이 우선 탐색은 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전의 정점으로 돌아가는 방식의 알고리즘이다.
깊이 우선탐색은 stack을 사용한다.

우선 탐색 Flow

예를 들어 아래와 같은 그래프를 깊이 우선 탐색으로 탐색해보자

[1] 현재 정점: 1

해당 정점을 탐색한 후 check[i]을 true로 만들어준다. (stack에 집어넣는 순간)

i	1	2	3	4	5
check[i]	true	false	false	false	false

현재 스택

[2] 1을 탐색했으니 이제 1와 인접해있는 2와 3 중 하나를 탐색해본다.

i	1	2	3	4	5
check[i]	true	true	false	false	false

현재 스택

[3] 2를 탐색했으니 2와 인접해있는 것중 아직 check가 false인 4를 탐색해보자

i	1	2	3	4	5
check[i]	true	true	false	true	false

현재 스택

[4] 다음으로 4와 인접해있고 아직 check[i]가 false인 5를 탐색해보자.

i	1	2	3	4	5
check[i]	true	true	false	true	true

현재 스택

[5] 그 다음으로는 5에서 갈 수 있는 것이 없기 때문에 stack에서 5를 pop해주고 4로 돌아간다.

5를 pop하더라도 check[5]는 false로 바뀌는 것이 아니다.

i	1	2	3	4	5
check[i]	true	true	false	true	true

현재 스택

[6] 4에서는 인접한 것 중에서 check 가 false인 3을 방문할 수 있기 때문에 3을 탐색한다.

i	1	2	3	4	5
check[i]	true	true	true	true	true

현재 스택

[7] 이제 더 이상 방문할 수 있는 것이 없기 때문에 스택에서 하나씩 pop해준다.

현재 스택

[8] 스택에 아무것도 없는 상태가 되면 탐색이 끝난 것이다.

그렇다면 깊이 우선 탐색을 코드로 구현하면 어떻게 구현할 수 있을까?
stack을 명시적으로 사용하지 않고 재귀함수 호출로 구현할 수 있다.
전에 인접행렬과 인접리스트를 사용하여서 그래프를 구현할 수 있다고 했는데 깊이 우선탐색도 두가지를 사용하여 모두 구현할 수 있다.

1) 인접행렬을 사용하여 깊이 우선탐색 구현하기

  public static void dfs(int x) {
        if (c[x]) {
            return;
        }
        c[x] = true;
        System.out.print(x + " ");
        for (int i=1; i<=n; i++) {
            if (c[i] == false && a[x][i]==1) {
                dfs(i);
            }
        }
    }

해당 행렬 (a[x][i])가 1이라는 것은 인접해 있다는 뜻이고 check[i]가 false라는 것은 아직 탐색되지 않았다는 뜻이기 때문이다.
이 경우 시간복잡도는 O(V^2) 라고 할 수 있다 (V는 정점의 개수)
모든 정점을 돌면서 확인하고 총 V번 호출되기 때문이다.

2) 인접리스트를 사용하여 깊이 우선탐색 구현하기

  public static void dfs(int x) {
        if (c[x]) {
            return;
        }
        c[x] = true;
        System.out.print(x + " ");
        for (int y : a[x]) {
            if (c[y] == false) {
                dfs(y);
            }
        }
    }

이 경우 a[x] 즉 리스트에 저장되어 있는 인접한 항들을 하나씩 돌면서 check가 false일 경우 재귀로 함수를 다시 불러 구하는 것이다.
이 경우 시간복잡도는 O(|V|+|E|)라고 할 수 있다. 여기서 E는 간선의 개수이다. 모든 정점을 한 번씩 방문하고 간선 E개에 대해서 확인을 해주기 때문이다.
대체로 V<=E이기 때문에 시간복잡도는 O(E)라고 할 수 있다.

2. BFS (Breadth First Search) : 너비 우선 탐색

깊이 우선탐색에서 스택을 사용했다면, 너비 우선탐색에서는 큐를 사용한다.
큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식으로 탐색이 진행된다.

이것도 위의 깊이 우선탐색처럼 같은 그림을 사용해 큐로 생각해보자

[1] 1부터 탐색을 시작해보자

i	1	2	3	4	5
check[i]	true	false	false	false	false

현재 queue

[2] 1이 인접할 수 있는 2와 3을 queue에 넣어주고 해당 check를 true로 바꾸어준다

i	1	2	3	4	5
check[i]	true	true	true	false	false

현재 queue

[3] 1에 인접한 것들을 queue에 넣었으니 1을 pop 해준다.

현재 queue

[4] 다음으로 2와 인접해 있는 것들중 해당 check 배열이 false인 것들을 queue에 넣어주고 true로 바꾸어준다.

i	1	2	3	4	5
check[i]	true	ture	true	true	true

현재 queue

[5] 다음으로 2를 pop해준다.

현재 queue

[6] 다음 3과 인접해있으면서 해당 check가 false인 것들을 queue에 넣어준다. 여기부터는 이제 모든 check가 true이게 되므로 queue에 넣어줄 것들이 없다. 즉, 하나씩 pop을 해주면 되는 것이다.

현재 queue

queue는 이렇게 다 빌 때까지 pop을 해주면 된다.

너비 우선탐색 또한 인접행렬과 인접그래프를 사용하여 모두 다 구현할 수 있다.

1) 인접행렬을 사용하여 너비 우선탐색 구현하기

 public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        c[start] = true;
        while (!q.isEmpty()) {
            int x = q.remove();
            System.out.print(x + " ");
            for(int i=1; i<=n; i++){
                if (c[i] == false && a[x][i]==1) {
                    c[i] = true;
                    q.add(i);
                }
            }
        }
    }

이것은 위에 DFS에서 본 것처럼 시간복잡도가 O(V^2)라는 것을 알 수 있음. 모든 정점마다 다른 모든 정점을 구해보기 때문

2) 인접리스트를 사용하여 너비 우선탐색 구현하기

 public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        c[start] = true;
        while (!q.isEmpty()) {
            int x = q.remove();
            System.out.print(x + " ");
            for (int y : a[x]) {
                if (c[y] == false) {
                    c[y] = true;
                    q.add(y);
                }
            }
        }
    }

이것 또한 위의 DFS와 마찬가지로 시간복잡도는 O(V+E)가 나온다는 것을 알 수 있다.