DFS와 BFS

2016년 09월 23일 | Jeremy

DFS

깊이 우선 탐색(Depth-First Search, DFS) 은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법입니다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라갑니다. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아갑니다.

깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 돌아간다는 점입니다. 이것을 구현하기 위해서는 지금까지 거쳐온 정점들을 모두 저장해 둬야 하는데, 재귀 호출 을 이용하면 이와 같은 일을 간단하게 할 수 있습니다. 재귀 호출한 함수가 종료하면 호출한 위치로 다시 돌아가기 때문입니다.

BFS

너비 우선 탐색(Breadth First Search, BFS) 은 각 정점을 방문할 때마다 모든 인접한 정점들 을 검사합니다. 이 중 처음 보는 정점을 발견하면 이 정점을 방문 예정이라고 기록해 둔 뒤, 별도의 위치에 저장합니다. 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문하게 됩니다. 따라서 너비 우선 탐색의 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정됩니다.

이를 구현하는 간단한 방법은, 목록에 먼저 넣은 정점을 항상 먼저 꺼내는 것입니다. 시작점에서 멀리 있는 정점일수록 나중에 목록에 먼저 넣은 정점을 항상 먼저 꺼내는 것입니다. 시작점에서 멀리 있는 정점일수록 나중에 목록에 추가되기 때문입니다. 따라서 정점 목록으로 큐 를 사용하면 너비 우선 탐색의 조건을 만족시킬 수 있습니다.

예제의 풀이는 C++로 작성하였습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int> > board;
vector<bool> visited;

// 아직 방문하지 않았고, here에서 next로 간선이 이어져 있을 때
void dfs(int here) {
    visited[here] = true;
    cout << here << " ";
    for (int next = 1; next < board.size(); ++next) {
        if (false == visited[next] && 1 == board[here][next]) {
            dfs(next);
        }
    }
}

// 아직 방문하지 않았고, here에서 next로 간선이 이어져 있을 때
void bfs(int start) {
    queue<int> que;
    que.push(start);
    visited[start] = true;

    int here;
    while (!que.empty()) {
        here = que.front(); que.pop();
        cout << here << " ";
        for (int next = 1; next < board.size(); ++next) {
            if (false == visited[next] && 1 == board[here][next]) {
                que.push(next);
                visited[next] = true;
            }
        }
    }
}

int main() {
    int N, M, start;
    cin >> N >> M >> start;
    board.assign(N + 1, vector<int>(N + 1, 0));
    int from, to;
    for (int i = 0; i < M; ++i) {
        cin >> from >> to;
        board[from][to] = board[to][from] = 1;
    }

    visited.assign(N + 1, false);
    dfs(start); cout << endl;
    visited.assign(N + 1, false);
    bfs(start); cout << endl;

    return 0;
}